Description

我们有一个网格，横向有 $H$ 行，纵向有 $W$ 列。让 $(i, j)$ 表示从上往下数第 $i$ 行和从左往上数第 $j$ 列的正方形。 $(i, j)$ 包含一个整数 $A_{i,j}$ 。

高桥将从 $(1, 1)$ 出发，反复向右或向下移动一格，直到到达 $(H, W)$ 。它不允许离开网格。

这次移动的代价定义为

• 所穿越的 $H+W-1$ 个方格中 $K$ 个最大整数之和。

求可能的最小成本。

Format

Input

第一行输入三个空格隔开的整数 $H,W,K$

接下来输入 $H$ 行每行 $W$ 个空格隔开的数字代表 $A_{i,j}$

Output

输出答案

Samples

1 3 2
3 4 5

9

2 2 1
3 2
4 3

3

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

21

Explain Sample 1

只有一种遍历方式，遍历的方格从大到小依次包含整数 $5$ 、 $4$ 、 $3$ ，因此我们打印 $9(=5+4)$ 。

Explain Sample 2

按此顺序遍历 $(1,1)$ 、 $(1,2)$ 、 $(2,2)$ ，即可获得最小成本。

Limitation

• $1 \leq H,W \leq 30$
• $1 \leq K<H+W$
• $1 \leq A_{i,j} \leq 10^9$
• 所有输入值均为整数。