페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1827

다트(Dart) 1s 256MB

문제

다트 게임을 하다 평범한 점수 계산에 싫증이 난 세영이는 새로운 게임 규칙을 생각해 내었다. 그 규칙은 아래와 같다.

  • 표적을 향해 최대 4발의 다트를 던질 수 있으나 한 발도 안 던져도 된다.

  • 표적은 N 개의 부분으로 구분되어 있고 각 부분에는 P_1, \cdots , P_n의 점수가 적혀있다.

  • 다트가 박힌 곳의 점수들을 합한 것이 최종 점수가 된다.

    • 하지만 제한 점수 M 이하이어야 한다.

    • 제한 점수 M을 초과할 경우 획득한 점수는 0이 된다.

표적의 점수들과 제한 점수 M이 주어질 때 얻을 수 있는 점수의 최대값을 구하는 프로그램을 작성하시오.


입력

첫 행에 표적의 나누어진 부분의 개수 N과 제한 점수 M 이 공백으로 구분하여 주어진다. ( 1 ≤ N ≤ 1,000) ( 1 ≤ M ≤ 200,000,000)

두 번째 행부터 N 개의 행에 걸쳐 표적의 각 부분의 점수 P_i ( 1 ≤ P_i ≤ 100,000,000)가 주어진다.


출력

4발 이하의 다트를 던질 때 얻을 수 있는 점수의 최대값을 구하는 프로그램을 작성하시오.


부분문제

번호 점수 조건
#120점

N\le100

#250점

N\le300

#330점

추가 제약 조건 없음


예제 #1

4 50

3

14

15

9
48

15점을 3번 맞추고 3점을 한 번 맞추면 합이 48점이 되며 얻을 수 있는 최대값이다.


예제 #2

3 21

16

11

2
20

16점을 1번, 2점을 2번 맞추면 20점이 되며 얻을 수 있는 최대값이다.



출처

JOI 2008 3번
로그인해야 코드를 작성할 수 있어요.