Bajtka 的爸爸煎了许多煎饼，并将它们堆成了 $n$ 堆，每堆有 $m$ 个煎饼。每一堆煎饼都是按大小排列的（最大的煎饼在最底部）。爸爸允许 Bajtek 吃掉其中的 $k$ 个煎饼。为了避免厨房里一片狼藉，Bajtek 只能吃掉每堆最上面的煎饼（他不能从底部取出最大的煎饼，因为爸爸担心这会导致煎饼散落在整个厨房里）。

Bajtek 很快意识到这些规则对他不利——毕竟最大的煎饼都在堆的底部——于是他迅速将其中一些堆翻转了过来。他本想把所有的堆都翻转，但没来得及，现在爸爸正警惕地注视着他的一举一动。因此，Bajtek 必须计划如何吃掉总大小尽可能大的 $k$ 个煎饼。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($n, m \ge 1; n \cdot m \le 300\,000; 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$ 个煎饼的最大总大小。

样例

输入 1

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

输出 1

11

输入 2

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

输出 2

4999999999999

说明

在第一个样例中，为了吃掉总大小为 11 的煎饼，Bajtek 可以例如吃掉第一堆中的所有三个煎饼（大小分别为 1, 2 和 3），以及最后一堆中最上面的两个煎饼（大小分别为 3 和 2）。可以证明，Bajtek 无法吃掉总大小超过 11 的煎饼。

在第二个样例中，Bajtek 可以吃掉除一个以外的所有煎饼。对他来说，留下第二堆最底下的那个煎饼是最划算的。