You have an infinite amount of protons, each with a positive charge of ~+e~ 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 ~N~ nodes, where the ~i~-th node has a potential energy of ~h_i~. 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 ~i~-th node, there are a ~p_i~ 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 ~j~-th pipe will overcome an external force and lose ~a_{i,j}~ units of energy.

At the ~i~-th node, there are a ~q_i~ 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 ~j~-th pipe will overcome an external force and lose ~b_{i,j}~ units of energy.

There are ~M~ one-way pipes inside the machine, the ~i~-th connecting pipe connecting points ~u_i~ and ~v_i~. The one-way pipes allow for protons to be transferred from node ~u_i~ to node ~v_i~. 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 ~i~-th pipe of point ~x~, and goes out from the ~j~-th pipe at point ~y~, the energy it loses to the machine is ~(h_x - h_y - a_{x,i} - b_{y,j})~.

Find the maximum sum of energy lost from the protons.

Input Specifications

The first line will contain two space-separated integers, ~N (1 \leq N \leq 2000)~ and ~M (0 \leq M \leq 2 \times 10^4)~, the number of nodes in the machine, and the number of connected one-way pipes in the machine, respectively.

The next line will contain ~N~ space-separated integers, the ~i~-th integer representing ~h_i (1 \leq h_i \leq 10^8)~, the potential energy of the ~i~-th node.

The next ~M~ lines will contain two positive space-separated integers, ~u_i~ and ~v_i (1 \leq u_i, v_i \leq N)~, representing a one-way pipeline.

The next ~N~ lines will first contain a positive integer ~p_i (1 \leq p_i \leq 2000)~, followed by ~p_i~ non-negative integers, where the ~j~-th integer represents ~a_{i,j} (1 \leq a_{i,j} \leq 10^6)~.

The next ~N~ lines will first contain a positive integer ~q_i (1 \leq q_i \leq 2000)~, followed by ~q_i~ non-negative integers, where the ~j~-th integer represents ~b_{i,j} (1 \leq b_{i,j} \leq 10^6)~.

Output Specifications

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

Subtasks

Subtask 1 [20%]

~N \leq 100~

~M \leq 500~

~h_i \leq 10^4~

~p_i, q_i \leq 200~

~a_{i,j}, b_{i,j} \leq 200~

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