두 그루의 사과 나무( 1 번 나무, 2 번 나무) 가 있고 , 원숭이가 최초에 있는 지점은 1 번 나무.

1 분 간격으로 두 사과나무 중 하나에서 사과가 떨어지고 , 왔다리 갔다리 할수 있는 최대 횟수가 주어질 때 최대로 먹을 수 있는 사과의 개수를 구하는 것이 문제. (원숭이가 빨라서 사과나무를 이동하는 시간은 없고 , 이동 횟수를 모두 사용할 필요도 없음)

예로 7 분 동안 , 최대 2 번 이동 가능하고 , 매 분 마다 떨어지는 나무 번호가 주어질 때

1 분  2 번 나무
2 분  1
3 분  1
4 분  2
5 분  2
6 분  1
7 분  1

• 1 분에는 1 번 나무에 그래로 ( 2 번 나무에 떨어지는 사과나무 버림)
• 2 분 , 3 분에서 떨어지는 사과를 받아먹고 , 이동해서
• 4 분 , 5 분에 떨어지는 사과를 받아먹고 , 이동해서
• 6 분, 7 분에 떨어지는 사과를 받아먹으면

입력

출력

입출력 예

입력

7 2 
2
1
1
2
2
1
1

출력

6

출처: USACO 2004 November