C - Darts

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c

問題
あなたは以下のルールでダーツゲームをすることになった．
あなたは，矢を的（まと）に向かって 4 本まで投げることができる．必ず
しも 4 本全てを投げる必要はなく，1 本も投げなくてもかまわない．的
は N 個の部分に区切られていて，各々の部分に点数 P1, · · · , PN が書か
れている．矢が刺さった場所の点数の合計 S があなたの得点の基礎とな
る．S があらかじめ決められたある点数 M 以下の場合は S がそのまま
あなたの得点となる．しかし，S が M を超えた場合はあなたの得点は
0 点となる．
的に書かれている点数と M の値が与えられたとき，あなたが得ることのできる
点数の最大値を求めるプログラムを作成せよ．
入力
入力ファイルのファイル名は input.txt である．
1 行目には，整数 N(1 5 N 5 1000) と M(1 5 M 5 200000000 = 2 × 108
) がこ
の順に空白区切りで書かれている．2 行目以降の第 1 + i 行目 (1 5 i 5 N) には，
Pi(1 5 Pi 5 100000000 = 108
) が書かれている．
採点用データのうち, 配点の 20% 分は N 5 100 を満たし，配点の 50% 分は
N 5 300 を満たす．
出力
出力ファイルのファイル名は output.txt である．
output.txt は 1 行だけからなり，あなたが得ることのできる点数の最大値を含む．

入出力の例
例 1
input.txt
4 50
3
14
15
9
output.txt
48
この例では，15 点の部分に 3 本，3 点の部分に 1 本の矢が刺さった場合にあなたの
得点は最大になり，その得点は 48 点である．
例 2
input.txt
3 21
16
11
2
output.txt
20
この例では，16 点の場所に 1 本，2 点の場所に 2 本の矢が刺さった場合にあなたの
得点は最大になり，その得点は 20 点である．

