P4473 [国家集训队] 飞飞侠

来源：国家集训队 2011 何朴藩

飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个 $N\times M$ 的矩形方阵，每个格子代表一个街区。 然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。 每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。 我们设第 $i$ 行第 $j$ 列的弹射装置有 $A_{i,j}$ 的费用和 $B_{i,j}$ 的弹射能力。并规定有相邻边的格子间距离是 $1$。那么，任何飞飞侠都只需要在 $(i,j)$ 支付 $A_{i,j}$ 的费用就可以任意选择弹到距离不超过 $B_{i,j}$ 的位置了。如下图  （从红色街区交费以后可以跳到周围的任意蓝色街区。） 现在的问题很简单。有三个飞飞侠，分别叫做 $X, Y, Z$。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你 $3$ 个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。（费用相同时优先 $X$，次优先 $Y$）

无

无

对于 $20\%$ 的数据，$N, M\leq 10$，$B_{i,j}\leq 20$。 对于 $40\%$ 的数据，$N, M \leq 100$，$B_{i,j}\leq 20$。 对于 $100\%$ 的数据，$1\leq N, M\leq 150$，$0\leq B_{i, j}\leq 10^9$，$0\leq A_{i, j}\leq 1000$。