题目描述

假定你是李华。

作为一名优秀的文科生，你最近学习了电学。

你有 $\infty$ 个电荷量为 $+e$，动能足够大的点电荷，要将其中的一部分通入一个机器，并通出等量点电荷。最大化机器运作后电荷的动能之和。

机器可以看作 $n$ 个节点，第 $i$ 个点电势为 $h_i \,\mathrm{V}$。

第 $i$ 个点有 $p_i$ 根管道可以从该点通入点电荷，在整个过程中每根管道最多通入一个点电荷，其中从第 $j$ 根管道通入的点电荷会克服外力做 $a_{i,j} \,\mathrm{eV}$ 的功。

第 $i$ 个点有 $q_i$ 根管道可以从该点通出点电荷，在整个过程中每根管道最多通出一个点电荷，其中从第 $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}$）

输入格式

第一行两个正整数 $n,m$

接下来一行 $n$ 个整数，第 $i$ 个数为 $h_i$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$ 描述一条单向管道。

接下来 $n$ 行，第 $i$ 行第一个正整数 $p_i$，接下来 $p_i$ 个非负整数，第 $j$ 个表示 $a_{i,j}$

接下来 $n$ 行，第 $i$ 行第一个正整数 $q_i$，接下来 $q_i$ 个非负整数，第 $j$ 个表示 $b_{i,j}$

输出格式

输出一个非负整数表达答案。

样例

输入

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

输出

6

数据范围与提示

对于 $100\%$ 的数据，保证 $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\} < 4$