P6797 "StOI-2" The Immortal Fugitive

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.

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.

One positive integer, the minimum value.

## 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