配点: 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 点。