あなたは李華（Li Hua）である。

文系学生として優秀なあなたは、最近電気学を学んだ。

あなたは電荷量 $+e$、十分な運動エネルギーを持つ点電荷を無限個持っている。そのうちの一部をある機械に投入し、同数の点電荷を排出する。機械の動作後に得られる点電荷の運動エネルギーの総和を最大化せよ。

機械は $n$ 個のノードからなるとみなすことができ、第 $i$ 番目のノードの電位は $h_i \,\mathrm{V}$ である。

第 $i$ 番目のノードには、そのノードへ点電荷を投入するためのパイプが $p_i$ 本ある。プロセス全体を通じて、各パイプからは最大で 1 つの点電荷しか投入できない。第 $j$ 番目のパイプから投入された点電荷は、外力に抗して $a_{i,j} \,\mathrm{eV}$ の仕事を行う。

第 $i$ 番目のノードには、そのノードから点電荷を排出するためのパイプが $q_i$ 本ある。プロセス全体を通じて、各パイプからは最大で 1 つの点電荷しか排出できない。第 $j$ 番目のパイプから排出された点電荷は、外力に抗して $b_{i,j} \,\mathrm{eV}$ の仕事を行う。

機械内部には $m$ 本の単方向パイプが接続されている。第 $i$ 番目のパイプは $u_i$ と $v_i$ を結んでおり、点電荷を $u_i$ から $v_i$ へ運ぶことができる（回数制限はない）。機械内部の他の力は仕事をせず、あなたは機械を通じて各点電荷の運動軌道を操作できると仮定する。

投入された各点電荷は必ず排出されなければならず、機械内部の他の力は仕事をしない。すなわち、ある点電荷がノード $x$ の第 $i$ 番目のパイプから入り、ノード $y$ の第 $j$ 番目のパイプから出た場合、機械がその点電荷に対して行う仕事は $(h_x - h_y - a_{x,i} - b_{y,j}) \,\mathrm{eV}$ となる。

運動エネルギーの増加量の総和（単位：$\mathrm{eV}$）の最大値を求めよ。

入力形式

第一行に2つの正整数 $n, m$ が与えられる。

続く一行に $n$ 個の整数が与えられ、第 $i$ 番目の数は $h_i$ である。

続く $m$ 行に、各行2つの正整数 $u_i, v_i$ が与えられ、単方向パイプを表す。

続く $n$ 行に、各行の最初の正整数が $p_i$ であり、続く $p_i$ 個の非負整数が $a_{i,j}$ を表す。

続く $n$ 行に、各行の最初の正整数が $q_i$ であり、続く $q_i$ 個の非負整数が $b_{i,j}$ を表す。

出力形式

答えである非負整数を出力せよ。

入出力例

入力 1

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

出力 1

6

制約

すべてのデータにおいて、$1 \le u_i, v_i \le n$、$0 \le m, p_i, q_i, a_{i,j}, b_{i,j}, h_i$ を満たす。ここで $a_{i,j}, b_{i,j}, h_i$ は対応する範囲内で等確率にランダム生成され、その他も何らかの方法でランダムに生成される。spfa 等のアルゴリズムを意図的にハックするようなケースは含まれない。

特殊性質 A：$|u_i - v_i| = 1$

特殊性質 B：$m = n - 1, u_i < v_i, v_i = i + 1$

特殊性質 C：$\min \{u_i, v_i\} \le 4$

注記

本問題の入出力規模が大きいため、追加でIOテンプレートを配布する。

この圧縮ファイルには5つのサンプルとIOテンプレートが含まれている。