시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB44202071.429%

문제

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

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

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

입력

標準入力から以下のデータを読み込め.

  • 1 行目には,整数 N, M が空白を区切りとして書かれている.これは,的が N 個の部分に区切られて いて,あらかじめ決められた点数が M であることを表す.
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には,整数 Pi が書かれている.これは的の i 番目の部分に書か れている点数が Pi であることを表す.

출력

標準出力に,あなたが得ることのできる点数の最大値を 1 行で出力せよ.

제한

  • 1 ≤ N ≤ 1 000.
  • 1 ≤ M ≤ 200 000 000.
  • 1 ≤ Pi ≤ 100 000 000.

서브태스크

번호배점제한
120

N ≤ 100.

230

N ≤ 300.

350

追加の制限はない.

예제 입력 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 点である.

채점 및 기타 정보

  • 예제는 채점하지 않는다.