LCC '21 Contest 6 S5 - Energy Machine

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

You have an infinite amount of protons, each with a positive charge of and enough kinetic energy to pass it through a machine. You want to pass some of these protons into a machine and pass out an equal amount of protons. Additionally, you want to maximize the sum of the energy lost from the protons in the machine.

The machine can be seen as nodes, where the -th node has a potential energy of . Nodes may have input pipes, output pipes or both. Input pipes will allow protons to enter through that node and output pipes will allow protons to exit through that node.

At the -th node, there are a number of input pipes from which protons can be passed into. In the whole process, at most one proton can passed through each input pipe, and the proton that goes through the -th pipe will overcome an external force and lose units of energy.

At the -th node, there are a number of output pipes from which protons can be passed out of. In the whole process, at most one proton can passed through each output pipe, and the proton that goes through the -th pipe will overcome an external force and lose units of energy.

There are one-way pipes inside the machine, the -th connecting pipe connecting points and . The one-way pipes allow for protons to be transferred from node to node . For example, a proton can enter at node 1 through an input pipe, that proton can then be transferred from node 1 to 3 through a one-way pipe and it can exit through the output pipe at node 3. There is no limit on the number of times protons can be transferred.

Every proton that enters the machine must exit. Additionally, the other forces in the machine do no work. That is, if a proton enters from the -th pipe of point , and goes out from the -th pipe at point , the energy it loses to the machine is .

Find the maximum sum of energy lost from the protons.

Input Specifications

The first line will contain two space-separated integers, and , the number of nodes in the machine, and the number of connected one-way pipes in the machine, respectively.

The next line will contain space-separated integers, the -th integer representing , the potential energy of the -th node.

The next lines will contain two positive space-separated integers, and , representing a one-way pipeline.

The next lines will first contain a positive integer , followed by non-negative integers, where the -th integer represents .

The next lines will first contain a positive integer , followed by non-negative integers, where the -th integer represents .

Output Specifications

Output a single non-negative integer representing the maximum sum of energy lost from the protons.

Subtasks

Subtask 2 [80%]

No additional constraints.

Sample Input

3 4
3 9 2
1 1
2 3
3 3
3 2
1 2
1 0
1 2
1 1
1 2
1 1

Sample Output

6

Comments

There are no comments at the moment.