問題
다트 게임을 하다 평범한 점수 계산에 싫증이 난 세영이는 새로운 게임 규칙을 생각해 내었다. 그 규칙은 아래와 같다.
표적을 향해 최대
4 발의 다트를 던질 수 있으나 한 발도 안 던져도 된다.
표적은
N 개의 부분으로 구분되어 있고 각 부분에는P_1, \cdots , P_n 의 점수가 적혀있다.다트가 박힌 곳의 점수들을 합한 것이 최종 점수가 된다.
하지만 제한 점수
M 이하이어야 한다.제한 점수
M 을 초과할 경우 획득한 점수는0 이 된다.
표적의 점수들과 제한 점수 M이 주어질 때 얻을 수 있는 점수의 최대값을 구하는 프로그램을 작성하시오.
輸入
첫 행에 표적의 나누어진 부분의 개수
두 번째 행부터
輸出
4발 이하의 다트를 던질 때 얻을 수 있는 점수의 최대값을 구하는 프로그램을 작성하시오.
子任務
| 編號 | 分數 | 條件 |
|---|---|---|
| #1 | 20分 | |
| #2 | 50分 | |
| #3 | 30分 | 추가 제약 조건 없음 |
範例 #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번
需要登入才能撰寫程式碼。