[AdditionalFile5679.zip](file://AdditionalFile5679.zip?type=additional_file)

#5679. 「PA 2026」Stosy naleśników

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 2 Stosy naleśników

Bajtek 的爸爸摊了许多煎饼，并将它们叠成了 $n$ 堆，每堆有 $m$ 个。每一堆里的煎饼都按大小排列（最大的煎饼在堆底）。Bajtek 被允许吃掉其中 $k$ 个煎饼。为了不让厨房变乱，Bajtek 只能吃每一堆最上面的煎饼（他不能直接取出堆底最大的煎饼，因为爸爸担心这样做会导致煎饼散落得到处都是）。

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

输入格式

第一行输入包含三个整数 $n, m$ 和 $k$ $(n, m \geq 1; n \cdot m \leq 300000; 1 \leq k \leq n \cdot m)$，分别表示煎饼堆的数量、每堆煎饼的数量以及 Bajtek 被允许吃掉的煎饼总数。

接下来的 $n$ 行包含堆的描述；第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, \ldots, a_{i, m}$ $(1 \leq a_{i, j} \leq 10^{12})$。数值 $a_{i, j}$ 表示第 $i$ 堆中从上往下数的第 $j$ 个煎饼的大小。对于每一堆 $i$，满足 $a_{i, j} \geq a_{i, j+1}$ 对所有 $j$ 成立，或者 $a_{i, j} \leq a_{i, j+1}$ 对所有 $j$ 成立。

输出格式

输出一个整数，表示 Bajtek 能吃到的 $k$ 个煎饼的最大总大小。

样例 1

输入

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

输出

11

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

样例 2

输入

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

输出

4999999999999

在第二个样例中，Bajtek 可以吃掉除一个煎饼外的所有煎饼。最划算的做法是不吃第二堆最底下的那个煎饼。