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