Problem L
University Zoning

In an effort to contain a recent pandemic, a certain university has decided to implement a zoning system. The school campus is a rectangular plot of land and is divided into a grid with $R$ rows and $C$ columns. Rows and columns are numbered from $1$ to $R$ and $C$ respectively. The top-most row is the first row, and the left-most column is the first column. Each of the $F$ faculties has been allocated some grid cells. For convenience, each of the $F$ faculties have unique code numbers from $1$ to $F$ inclusive. Cells belong to at most $1$ faculty.

$S$ students, each with unique student number $D$, have enrolled in the university. Within a faculty, the student with the smallest student number will occupy the top-most unoccupied cell. If there are ties, the left-most available cell will be assigned to that student. This repeats for the student with the next smallest student number, until every student within that faculty has been assigned to a cell. Every faculty has enough spots for its enrolled students, and has at least one enrolled student.

On the first day of school, students were found to be in random cells all over the campus. Some cells might even contain more than one student! You are the safety officer, and have been given the following task: There must be at least $G$ faculties with their compliance target met. A compliance target is met if there is at least $T$ students found in their assigned cells. Every faculty has an assigned $T$ value. To complete the task, you will instruct students to move to their assigned cells. Students can take $1$ step to move to any of the four adjacent cells (up, down, left, right), can occupy cells belonging to other faculties, can occupy the same cell as other students and can walk past other students if necessary. If a student is in their assigned cell, that student is counted as being in their assigned cell, even if there are other students currently occupying it. What is the minimum number of steps the students have to take in order for you to complete your task?

Refer to the diagrams below for clarification on how the assignment works for the sample inputs.

Input

The first line contains five integers $1 \le R \le 10^9$, $1 \le C \le 10^9$, $1 \le F \le 10^2$, $1 \le S \le 10^5$ and $0 \le G \le F$. The next $F$ lines describes the cells assigned to each faculty, from faculty $1$ to faculty $F$ in ascending order. Each of the $F$ lines contains an integer $1 \le K \le 10^3$ the number of cells assigned to that faculty. The rest of the line contains $K$ integer pairs $r_1\; c_1\; r_2\; c_2\; \ldots \; r_ k\; c_ k$, each $r\; c$ pair describing the row and column coordinates of a cell allocated to that faculty. The next $S$ lines contain four integers: $r\; c$, the coordinates of each of the students on the first day, student number $1 \le D \le 10^9$ and $f$, the faculty that student is enrolled in. All cell coordinates lie inside the school boundaries. The final line contains the $T$ values ($0 \leq T \leq E$ where $E$ is the total number of students enrolled in that faculty) for each faculty, from faculty $1$ to faculty $F$.

Output

Output the minimum number of steps required.

Subtasks

1. ($2$ Points): Sample.

2. ($12$ Points): $T = E$ for all faculties, $G = F$, $R = 1$.

3. ($20$ Points): $T = E$ for all faculties, $G = F$.

4. ($27$ Points): $T = E$ for all faculties.

5. ($39$ Points): No additional constraint.

3 5 2 5 2
4 1 1 1 2 1 5 2 1
3 2 5 3 3 3 5
1 1 1 1
1 3 2 1
1 5 3 1
2 5 4 2
3 3 5 2
3 2

1

3 5 1 2 1
2 1 1 1 2
3 5 1 1
1 3 2 1
1

1