A 市可以看成一个 的网格,现在令 为第 行第 列的格子。
在这之前,人们的出行一般只通过网格图上原有的边来行走,但这时候有人想到如果修起从一个格子到另一个格子的直通隧道,那么人们的出行将会方便许多。
因此他向政府申请修建一个这样的直通隧道。但政府不想花费太多的钱,因此只希望修一条隧道,且想知道最少需要花多少钱来修建这一条隧道。
隧道的修建的步骤如下:首先选择两个不同的格子 ,然后分别花费 的钱来挖洞,然后就需要在地底挖隧道,这时候的需要的钱是 。因此,修建一条隧道的总花费是 。
第一行输入三个整数 ,其含义如题面所示。
接下来 行每行输入 个整数 ,表示在 处挖洞的代价。
输出一个整数,表示最小花费。
3 4 2 1 7 7 9 9 6 3 7 7 8 6 4
10
选择 与 之间挖隧道,那么花费就是 。