34551번 - 사과 농장

문제

홍익이는 사과 농장을 가지고 있다. 농장은 가로, 세로의 길이가 각각 $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()을 사용해야 합니다.