T603020 『RETOI』Round1-pipilong2024-损友 Partner

~~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)$，其中 “$=>$” 表示依靠传送门，“$->$” 表示不依靠传送门，也就是自己走。 #### 数据范围 **本题采用捆绑测试**。 - 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^5$。