← 返回题目列表

AtCoder · joi2008ho_c

C. 飞镖

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

配点: 20 点

您将按照以下规则玩飞镖游戏。

你将箭瞄准目标。 4 你甚至可以扔书。不一定 4 你不必扔掉所有的书;1 你也不必扔掉书。目标是 它分为 N 部分,每个部分都有一个分数。 写入 P_1,\ldots,P_N 。箭头击中的总点数 S 是您分数的基础。S 是预定分数 M 在以下情况下: S 原样 这是你的分数。然而, 如果您超过S 是 M ,您的分数将为 0 成为重点。

和分数写在 编写一个程序,在给定 M 的情况下找到您可以获得的最大点数。


入力

输入文件的文件名是 input.txt 。

1 行包含一个整数 N (1\leqq N\leqq 1000)和 M (1\leqq M\leqq 200000000=2\times 10^8)按此顺序写入,并用空格分隔。2 行后行 1 + i 行目 (1\leqq i\leqq N)有 P_i (1 \leqq P_i\leqq 100000000=10^8)被写入。

评分数据中,分配的分数 20 % 是 N \leqq 100 满意,积分为 50 % 是 N \leqq 300 很满意。

出力

输出文件的文件名是 output.txt 。

output.txt 仅由一行组成,包含您可以获得的最大点数。


入力例 1

4 50
3
14
15
9

出力例 1

48

在此示例中,15 此时 3 本,3 此时 1 如果书本箭头击中你,你的分数将最高; 48 点。


入力例 2

3 21
16
11
2

出力例 2

20

在此示例中,16 在该点 1 本,2 在该点 2 如果书本箭头击中你,你的分数将最高; 20 点。