다트 (Darts)

면접 대비

시간 제한1초메모리 제한256 MB

요약

최대 4개의 화살과 N개 영역 점수가 주어질 때, M을 넘지 않는 최대 합을 구하고 모든 합이 M을 넘으면 0을 출력한다.

문제

다음 규칙에 따라 다트 게임을 한다.

과녁을 향해 화살을 최대 4개까지 던질 수 있다. 반드시 4개를 모두 던질 필요는 없으며, 한 개도 던지지 않아도 된다.
과녁은 $N$ 개의 부분으로 나뉘어 있고, 각 부분에는 점수 $P_1, \dots, P_N$ 이 적혀 있다. 한 부분에 여러 화살이 꽂혀도 되며, 그때마다 그 부분의 점수가 더해진다.
화살이 꽂힌 부분들의 점수 합 $S$ 가 득점의 기준이 된다.
미리 정해진 점수 $M$ 에 대해, $S \le M$ 이면 $S$ 가 그대로 득점이 된다. 그러나 $S$ 가 $M$ 을 초과하면 득점은 $0$ 점이 된다.

과녁에 적힌 점수들과 $M$ 의 값이 주어질 때, 얻을 수 있는 득점의 최댓값을 구하는 프로그램을 작성하여라.

표준 입력으로 다음 데이터가 주어진다.

첫째 줄에 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. 과녁이 $N$ 개의 부분으로 나뉘어 있고, 미리 정해진 점수가 $M$ 임을 뜻한다.
이어지는 $N$ 개의 줄 중 $i$ 번째 줄 ( $1 \le i \le N$ )에는 정수 $P_i$ 가 주어진다. 이는 과녁의 $i$ 번째 부분에 적힌 점수가 $P_i$ 임을 뜻한다.

얻을 수 있는 득점의 최댓값을 한 줄에 출력한다.