아빠 원숭이 한 마리가 가족들의 양식을 얻기 위해 숲에 도달했다.

나무들이 일렬로 늘어서 있으며 각 나무에는 맛있는 열매들이 달려있다.

원숭이는 나무들을 늘어선 차례대로 방문하면서 열매를 따오려고 한다.

나무에 올라가면 열려있는 열매들을 모두 따올 수 있지만 에너지가 1만큼 감소하고,

나무에 올라가지 않고 그 시간만큼 나무 밑에서 잠시 쉬어가면 에너지가 1만큼 상승한다.

단, 나무 위에는 원숭이를 싫어하는 송충이들이 원숭이를 괴롭히려고 하기 때문에 일단 에너지가 상승을 하면 지체 없이 그 나무에서 떠나야 한다.

즉 한 개의 나무를 지날 때마다, 에너지가 1 감소하면서 그 나무에 있는 열매를 모두 따거나 열매를 따지 않고 에너지를 1 보충하거나 둘 중의 하나를 선택할 수 있다.

만약 에너지가 0이라면 열매를 딸 수가 없고 반드시 쉬어가면서 에너지를 보충해야 한다.

원숭이가 처음에 숲에 도달했을 때는 최대 에너지를 가지고 있으며 최대 에너지일 때에는 아무리 쉬어도 더 이상 에너지가 증가하지는 않는다.

주어진 정보를 가지고 아빠 원숭이가 얼마나 많은 열매를 얻을 수 있는지 알아보는 프로그램을 작성하라.

[부분문제]

입력데이터의 20%는 N <= 20 이고 M은 2이다.

입력데이터의 40%는 N <= 100 이고 M <= 20 이다.

열매따기2 timer 1s memory 128MB

열매따기2 1s 128MB