Problem Description

Balboa wants to escape to an immortal cause—discovering the Pacific Ocean.

Now Balboa is at position $(1,1)$ in a matrix, and the Pacific Ocean is at $(n,m)$. The danger value at position $(i,j)$ is $d_{i,j}$. He has captured $k$ Indians. The $i$-th person knows about the range $[ax_i,ay_i] [bx_i,by_i]$ (a rectangle with $(ax_i,ay_i)$ as the top-left corner and $(bx_i,by_i)$ as the bottom-right corner). If Balboa brings this person along, there will be no danger within this range.

Because time is tight, Balboa moves in 4-connected directions, and he must visit exactly $n+m-1$ positions to reach the Pacific Ocean.

Now Balboa hopes to bring at most $w$ people, and at the same time minimize the sum of danger values. Find the minimum possible value.

Input Format

The first line contains $4$ positive integers $n$, $m$, $k$, $w$, with meanings as described above.

Next is an $n$-row $m$-column matrix, with meanings as described above.

Next are $k$ lines, each containing $4$ positive integers $ax_i$, $bx_i$, $ay_i$, $by_i$, with meanings as described above.

Output Format

One positive integer, the minimum value.

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

3

Hint

Sample Explanation

Choose the second person.

Path: (1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(4,4)

Danger values: the unprotected (4,3) and (4,4), which is $2+1=3$.

Constraints

This problem uses bundled testdata.

Subtask $1$ ($10$ points): $1 \leq n,m,k,w \leq 4$.
Subtask $2$ ($20$ points): $1 \leq n,m,k,w \leq 20$.
Subtask $3$ ($20$ points): $1 \leq n,m,k,w \leq 50$.
Subtask $4$ ($20$ points): all $d_{i,j}$ are the same.
Subtask $5$ ($30$ points): no special properties.

For all data: $1 \leq n,m,k \leq 200$, $1 \leq w \leq 100$, $0 \leq d_{i,j} \leq 10^8$, $1 \leq ax_i \leq bx_i \leq n$, $1 \leq ay_i \leq by_i \leq m$.

Note: the input order is slightly different from the statement.

Output Format

一个正整数，表示最小值。

Hint

Translated by ChatGPT 5