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