문제
아빠 원숭이 한 마리가 가족들의 양식을 얻기 위해 숲에 도달했다.
나무들이 일렬로 늘어서 있으며 각 나무에는 맛있는 열매들이 달려있다.
원숭이는 나무들을 늘어선 차례대로 방문하면서 열매를 따오려고 한다.
나무에 올라가면 열려있는 열매들을 모두 따올 수 있지만 에너지가 1만큼 감소하고,
나무에 올라가지 않고 그 시간만큼 나무 밑에서 잠시 쉬어가면 에너지가 1만큼 상승한다.
단, 나무 위에는 원숭이를 싫어하는 송충이들이 원숭이를 괴롭히려고 하기 때문에 일단 에너지가 상승을 하면 지체 없이 그 나무에서 떠나야 한다.
즉 한 개의 나무를 지날 때마다, 에너지가 1 감소하면서 그 나무에 있는 열매를 모두 따거나 열매를 따지 않고 에너지를 1 보충하거나 둘 중의 하나를 선택할 수 있다.
만약 에너지가 0이라면 열매를 딸 수가 없고 반드시 쉬어가면서 에너지를 보충해야 한다.
원숭이가 처음에 숲에 도달했을 때는 최대 에너지를 가지고 있으며 최대 에너지일 때에는 아무리 쉬어도 더 이상 에너지가 증가하지는 않는다.
주어진 정보를 가지고 아빠 원숭이가 얼마나 많은 열매를 얻을 수 있는지 알아보는 프로그램을 작성하라.
[부분문제]
입력데이터의 20%는 N <= 20 이고 M은 2이다.
입력데이터의 40%는 N <= 100 이고 M <= 20 이다.
입력
첫 줄에 나무의 수 N(1 ≤ N ≤ 10,000)과 에너지의 최댓값 M(1 ≤ M ≤ 500)이 주어진다.
둘째 줄부터 한 줄에 하나씩 각 나무별 열려있는 열매의 개수 Si (1 ≤ Si ≤ 1 000)이 주어진다.
출력
따올 수 있는 최대 열매의 개수를 출력한다.
예제
8 3
4
6
3
1
9
4
8
7
34
출처
KYIO2014(성결대)
로그인해야 코드를 작성할 수 있어요.