003 - ダーツ

問題

あなたは以下のルールでダーツゲームをすることになった.

あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ず しも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的 は N 個の部分に区切られていて,各々の部分に点数 P₁,..., P_N が書か れている.矢が刺さった場所の点数の合計 S があなたの得点の基礎とな る.S があらかじめ決められたある点数 M 以下の場合は S がそのまま あなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.

的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる 点数の最大値を求めるプログラムを作成せよ.

入力

入力ファイルのファイル名は input.txt である.

1 行目には,整数 N (1 ≤ N ≤ 1000) と M (1 ≤ M ≤ 200000000 = 2 × 10⁸)がこの順に空白区切りで書かれている.2 行目以降の第 1 + i 行目 (1 ≤ i ≤ N ) には, P_i (1 ≤ P_i ≤ 100000000 = 10⁸ ) が書かれている.

採点用データのうち, 配点の 20% 分は N ≤ 100 を満たし,配点の 50% 分は N ≤ 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 点である.