#1045. 修桥

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

A 市可以看成一个 的网格,现在令 为第 行第 列的格子。

在这之前,人们的出行一般只通过网格图上原有的边来行走,但这时候有人想到如果修起从一个格子到另一个格子的直通隧道,那么人们的出行将会方便许多。

因此他向政府申请修建一个这样的直通隧道。但政府不想花费太多的钱,因此只希望修一条隧道,且想知道最少需要花多少钱来修建这一条隧道。

隧道的修建的步骤如下:首先选择两个不同的格子 ,然后分别花费 的钱来挖洞,然后就需要在地底挖隧道,这时候的需要的钱是 。因此,修建一条隧道的总花费是

输入格式

第一行输入三个整数 ,其含义如题面所示。

接下来 行每行输入 个整数 ,表示在 处挖洞的代价。

输出格式

输出一个整数,表示最小花费。

样例

样例输入

3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

样例输出

10

样例解释

选择 之间挖隧道,那么花费就是

数据范围与提示

  • 对于 40% 的数据,
  • 对于 100% 的数据,