logo AlgoBeat OnlineJudge
登录 注册

#216031. [PA 2026] 堆煎饼 / Stosy naleśników

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

输入格式

输入的第一行包含三个整数 ),分别表示薄煎饼的摞数、每摞薄煎饼的数量以及Bajtek被允许吃的薄煎饼数量。

接下来 行是各摞的描述;第 行包含 个整数 )。数 表示第 摞从顶部数第 张薄煎饼的大小。对于每个 ,要么对所有 都有 ,要么对所有 都有

输出格式

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

样例

样例输入 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

数据范围与提示

示例说明:在第一个示例中,为了吃到总大小为 的薄煎饼,Bajtek可以吃第一摞的全部三张薄煎饼(大小依次为 ),以及最后一摞顶部的两张薄煎饼(大小依次为 )。可以证明,Bajtek无法吃到总大小超过 的薄煎饼。

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