← 返回比赛

已结束『RetOI』Round 1

← 上一题下一题 →

A5160 | $损友$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

~~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 的最小得分。

输入输出样例

输入 #1

4 6 4 2
1 2 3 0 0 6
6 3 0 0 3 6
3 2 3 0 8 6
2 1 2 3 1 10
1 2
3 4
2 3
4 5

输出 #1

C++ 编辑器

输入

输出