题目描述

巴尔博亚要逃遁到不朽的事业——发现太平洋。

现在巴尔博亚在一个矩阵的 $(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$ 。

注意：输入顺序与题目略有不同