Darts

Time Limit : 1 sec, Memory Limit : 65536 KB

ダーツ

問題

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

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

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

入力

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

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

採点用データのうち, 配点の 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 点である.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. N, M がともに 0 のとき入力の終了を示します.

Sample Input

4 50
3
14
15
9
3 21
16
11
2
0 0

Sample Output

48
20

Source: 7th Japanese Olympiad in Informatics , 2008-02-10
http://www.ioi-jp.org/