A75048.损友

lz 喜欢玩电子游戏。
期中考结束了，lz 考得一塌糊涂，于是他决定玩会儿游戏。
这个游戏由一个含 $n \times m$ 个格点的地图构成，我们称第 $i$ 行第 $j$ 个格点为 $(i,j)$，每个格点都有一个宝藏，它的价值为 $w_{i,j}$。
lz 从 $(1,1)$ 开始，每一次行动都可以选择向下走一格或是向右走一格，不能走出地图，走到 $(n,m)$ 为止。最后 lz 获得的得分就是 TA 一路上所得到的所有宝藏价值之和。

---

可故事并没有这么简单（雾，pzh 是 lz 的损友，TA 希望让 lz 雪上加霜，也就是让 lz 得分最小。
于是 pzh 花了 $114514$ 大洋买通了游戏管理员，管理员们决定为 lz 准备 $k$ 个传送门，分别安放在 $k$ 个不同的格点上，每个传送门之间均可以互相传送。
可无奈 lz 的智商有限，TA 最多只能传送 $p$ 次，现在请你帮忙算出 lz 该游戏的得分最小为多少？

输入共 $1 + n + k$ 行。
第一行四个整数，分别为 $n,m,k,p$，意义如题面所述。
接下来 $n$ 行，每行 $m$ 个整数，其中第 $i-1$ 行第 $j$ 个元素，表示 $w_{i,j}$。
最后 $k$ 行，每行两个正整数 $x,y$，表示 $(x,y)$ 上有一个传送门。

输出共一行一个正整数，表示 lz 的最小得分。

提示

题目描述中的三个 “TA” 并不是一个人。
凡是 lz 经过的格点，贪婪的 lz 一定会拿走宝藏。

样例解释

样例 #1

路径描述：$(1,1) -> (1,2) => (2,3) -> (2,4) -> (3,4) => (4,5) -> (4,6)$，其中 “$=>$” 表示依靠传送门，“$->$” 表示不依靠传送门，也就是自己走。

数据范围

本题采用不捆绑测试（ACGO 评测机不支持）。

• Subtask 1（10 points）：$n \le 10$，$m \le 10$。
• Subtask 2（20 points）：$n \le 50$，$m \le 50$，$k \lt 1$。
• Subtask 3（10 points）：$n \le 100$，$m \le 100$，$p \le 10$。
• Subtask 4（20 points）：$n \le 10^3$，$m \le 10^3$，$p \le 10$。
• Subtask 5（40 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^3$，$1 \le m \le 2 \times 10^3$，$0 \le k \le n \times m$，$0 \le p \le 10^8$，$0 \le w_{i,j} \le 10^{10}$。