사과 농장

홍익이는 사과 농장을 가지고 있다. 농장은 가로, 세로의 길이가 각각 $M$, $N$인 직사각형 모양이며, 왼쪽 아래 꼭짓점의 좌표는 $(0, 0)$, 오른쪽 위 꼭짓점의 좌표는 $(M, N)$이다. 농장은 한 변의 길이가 $1$인 정사각형 칸들로 구분되어 있으며, 오른쪽 위 꼭짓점의 좌표가 $(x, y)$인 칸에는 사과 $A\_{x, y}$개가 열려 있다.

홍익이는 '널리 이롭게 한다'는 홍익 정신을 실천하기 위해 자신의 사과 농장을 개방하여 다른 사람들이 수확할 수 있도록 했다. $K$명의 사람들이 모였고, 각 사람은 자신이 수확할 영역을 미리 정해 놓은 상태이다. $i$번째 사람이 정한 영역은 $R\_i$개의 정수 좌표 꼭짓점들로 이루어진 단순 직각 다각형 모양이다. 즉, 다각형의 각 변은 $x$축 또는 $y$축에 평행하며, 다각형의 두 선분은 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는다. 이때, 서로 다른 사람이 정한 영역끼리는 겹칠 수 있다.

모인 사람들 중에는 지인과 함께 온 사람들도 있는데, 이 사람들은 지인의 지인까지도 모두 알고 있다. 구체적으로, 두 사람 $X$와 $Y$가 서로 지인 관계이고 $Y$와 $Z$가 서로 지인 관계이면 $X$와 $Z$도 항상 서로 지인 관계이다.

홍익이는 사람들이 무질서하게 수확하는 것을 방지하기 위해 다음과 같은 규칙을 세웠다.

• 어떤 칸을 수확하려는 사람이 $1$명인 경우: 그 사람이 해당 칸의 사과를 모두 갖는다.
• 어떤 칸을 수확하려는 사람이 $2$명 이상인 경우: 해당 칸에 열려 있는 사과의 개수를 $c$, 해당 칸을 수확하려는 사람의 수를 $n$이라고 하자. 그 사람들이 모두 서로 지인 관계라면 각자 $\lfloor \frac{c}{n} \rfloor$ 만큼씩 사과를 나눠 갖는다. 그렇지 않다면 아무도 그 칸에서 사과를 가져가지 않는다.

위와 같은 규칙 아래에서 사람들이 수확을 할 때, 가장 많은 사과를 수확하는 사람은 몇 개의 사과를 갖게 되는지 구해보자.

첫째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 1\ 000$)

다음 $N$개의 줄에 걸쳐 각 칸마다 열린 사과의 수가 주어진다. $i$번째 줄에는 $M$개의 정수 $A\_{1,i}, A\_{2,i}, \cdots, A\_{M,i}$가 공백으로 구분되어 주어진다. ($0 \le A\_{x,y} \le 10^9$)

다음 줄에 $K$가 주어진다. ($1 \le K \le 1\ 000$)

다음 $K$개의 줄에 걸쳐 각 사람이 정한 수확 영역의 꼭짓점들의 좌표가 주어진다. $i$번째 줄에는 $1+2R\_i$개의 정수 $R\_i, x\_{i,1}, y\_{i,1}, x\_{i,2}, y\_{i,2}, \cdots, x\_{i,R\_i}, y\_{i,R\_i}$가 공백으로 구분되어 주어진다. $1 \le j \lt R\_i$인 정수 $j$에 대해 두 꼭짓점 $(x\_{i,j}, y\_{i,j})$와 $(x\_{i,j+1}, y\_{i,j+1})$을 잇는 선분이 존재하며, $(x\_{i,R\_i}, y\_{i,R\_i})$와 $(x\_{i,1}, y\_{i,1})$를 잇는 선분이 존재한다. 가로 선분이 연속되거나 세로 선분이 연속되는 경우는 주어지지 않으며, 각 수확 영역의 둘레의 길이는 $2(M+N)$을 넘지 않는다. ($0 \le x\_{i, j} \le M, 0 \le y\_{i,j } \le N$)

다음 줄에 지인 관계의 수 $P$가 주어진다. ($0 \le P \le \displaystyle\frac{K(K-1)}{2}$)

다음 $P$개의 줄에 걸쳐 각 지인 관계 정보가 주어진다. $i$번째 줄에는 두 정수 $p\_i, q\_i$가 공백으로 구분되어 주어진다. $p\_i$번째 사람과 $q\_i$번째 사람이 서로 지인임을 의미한다. 같은 관계가 두 번 이상 주어지지 않는다. ($1 \le p\_i \lt q\_i \le K$)

가장 많은 사과를 수확하는 사람이 갖게 되는 사과의 개수를 출력한다.

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고하세요.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.