← 返回题目列表

Codeforces · 148/E

E. 瓷器

中文机器翻译题面 查看原题

公主发脾气时通常会打碎一些具有收藏价值的瓷器。每一声愤怒的尖叫都伴随着一件物品被砸碎。

收藏的瓷器整齐地排列在n个架子上。每个架子内的物品都放置在一排,这样人们只能访问最外面的物品 - 最左边或最右边的物品,而不是架子中间的物品。一旦拿走了一个物品,就可以访问货架该侧的下一个物品(参见示例)。商品一旦被拿走,就无法返回货架。

您将获得所有项目的值。你的任务是找出公主的尖叫声对瓷器收藏品造成的最大损害。

输入

输入数据的第一行包含两个整数 n (1 ≤ n ≤ 100) 和 m (1 ≤ m ≤ 10000)。接下来的 n 行包含货架上物品的值:第一个数字给出了该货架上物品的数量(1 到 100 之间的整数(含)),后面是物品的值(1 到 100 之间的整数(含)),按照它们在货架上出现的顺序排列(第一个数字对应于最左边的物品,最后一个对应于最右边的物品)。保证项目总数至少为 m。

输出

输出 m 次尖叫的发脾气的最大总值。

示例

输入 #1

2 3
3 3 7 2
3 4 1 5

输出 #1

15

输入 #2

1 3
4 4 3 1 2

输出 #2

9

注意

在第一种情况下,有两个架子,每个架子上有三件物品。为了最大化所选物品的总价值,可以从第一个架子的左侧拿走两件物品,从第二个架子的右侧拿走一件物品。

在第二种情况下,只有一个架子,因此所有三件物品都从其中取出 - 两件来自左侧,一件来自右侧。