「StOI-2」不朽的逃亡者

巴尔博亚要逃遁到不朽的事业——发现太平洋。 现在巴尔博亚在一个矩阵的 $(1,1)$ 位置，太平洋在 $(n,m)$ ， $(i,j)$ 位置的危险值为 $d_i$$_j$ 。他现在抓到了 $k$ 个印第安人，第 $i$ 个人对 $[ax_i,ay_i] [bx_i,by_i]$ 的**范围**（ 以 $(ax_i,ay_i)$ 为左上角坐标，以 $(bx_i,by_i)$ 为右下角坐标的矩形 ）有了解，如果带上这个人，这一范围不会有危险。 由于时间紧迫，巴尔博亚必须只走 $n+m-1$ 个位置到达太平洋。 现在巴尔博亚希望最多带上的人数不超过 $w$ ，同时使危险值之和最小，求最小值。

第一行 $4$ 个正整数，$n$ , $m$ , $k$ , $w$ , 含义如题。 接下来是一个 $n$ 行 $m$ 列的矩阵，含义如题。 接下来 $k$ 行，每行 $4$ 个正整数，分别是 $ax_i$ ，$bx_i$ ， $ay_i$ , $by_i$ ，含义如题。

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

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

## 样例解释 选择第二人。 路径：`(1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(4,4)` 危险值: 没有受到保护的 `(4,3)`与`(4,4)` ，为 $2+1=3$。 ## 数据范围 #### 本题采用捆绑测试。 子任务 $1$（$10$ 分）：$1 \leq n,m,k,w \leq 4$。 子任务 $2$（$20$ 分） : $1 \leq n,m,k,w \leq 20$。 子任务 $3$（$20$ 分）：$1 \leq n,m,k,w \leq 50$。 子任务 $4$（$20$ 分）：所有 $d_{i,j}$ 均相同。 子任务 $5$（$30$ 分） : 无特殊性质。 对于所有数据：$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$ 。 注意：输入顺序与题目略有不同