당신은 리화(Li Hua)입니다.

훌륭한 인문계 학생으로서, 당신은 최근 전기학을 공부했습니다.

당신은 전하량이 $+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$개의 줄에는 각각 첫 번째 정수 $p_i$와 그 뒤에 $p_i$개의 음이 아닌 정수가 주어지며, $j$번째 수는 $a_{i,j}$를 나타냅니다.

다음 $n$개의 줄에는 각각 첫 번째 정수 $q_i$와 그 뒤에 $q_i$개의 음이 아닌 정수가 주어지며, $j$번째 수는 $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

참고

예제 2~5는 제공된 파일을 참조하십시오.

제한

모든 데이터에 대하여 $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 템플릿이 포함되어 있습니다.