题目描述

Bajtek的爸爸煎了很多薄煎饼。他将它们堆成了 $n$ 摞，每摞 $m$ 张薄煎饼。每摞薄煎饼按从大到小的顺序排列（即最大的薄煎饼在摞的底部）。他允许Bajtek吃其中 $k$ 张薄煎饼。为了避免厨房乱糟糟，Bajtek只能吃摞顶部的薄煎饼（他不能从底部取出最大的薄煎饼，因为爸爸担心这样会导致薄煎饼散落满厨房）。

Bajtek很快意识到这些规则对他不利——毕竟最大的薄煎饼在摞的底部——于是他迅速将其中几摞倒了过来。他本想把所有的都翻过来，但没来得及，而现在爸爸已经警惕地注视着他的每一个动作。因此，Bajtek必须规划如何尽可能多地吃薄煎饼。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$n,m \ge 1$；$n \cdot m \le 300000$；$1 \le k \le n \cdot m$），分别表示薄煎饼的摞数、每摞薄煎饼的数量以及Bajtek被允许吃的薄煎饼数量。

接下来 $n$ 行是各摞的描述；第 $i$ 行包含 $m$ 个整数 $a_{i,1}, \dots, a_{i,m}$（$1 \le a_{i,j} \le 10^{12}$）。数 $a_{i,j}$ 表示第 $i$ 摞从顶部数第 $j$ 张薄煎饼的大小。对于每个 $i$，要么对所有 $j$ 都有 $a_{i,j} \ge a_{i,j+1}$，要么对所有 $j$ 都有 $a_{i,j} \le a_{i,j+1}$。

输出格式

输出一个整数——Bajtek可以吃的 $k$ 张薄煎饼的最大总大小。

3 3 5
1 2 3
1 2 3
3 2 1

11

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

4999999999999

提示

示例说明：在第一个示例中，为了吃到总大小为 $11$ 的薄煎饼，Bajtek可以吃第一摞的全部三张薄煎饼（大小依次为 $1$、$2$ 和 $3$），以及最后一摞顶部的两张薄煎饼（大小依次为 $3$ 和 $2$）。可以证明，Bajtek无法吃到总大小超过 $11$ 的薄煎饼。

在第二个示例中，Bajtek可以吃除一张之外的所有薄煎饼。他最好留下第二摞底部的薄煎饼不吃。