구름 레이싱 게임이 있다. 게임의 규칙은 다음과 같다. 2차선의 두 줄의 길을 달리는 구름카가 있다. 구름카는 1초에 한칸씩 전진 하며 동전을 먹어야한다. 이 때, 동전은 한 칸에 하나씩 존재하며 두 줄중 한쪽에만 존재한다. 그리고 구름카는 최대 K(1≤K≤30)번만 차선변경을 할 수 있다. 이 때, 차선 변경에 드는 시간은 무시하며, 언제나 처음은 1차선에서 시작한다. 구름카가 T(1≤T≤1,000)초 동안 전진할 때, 구름카로 먹을 수 있는 동전의 최대 개수를 구하여라. 예를 들어, 아래의 입력 예제1의 경우는 10초 동안 2번의 차선 변경을 할 수 있다. 1번 줄에서 처음 두개의 동전을 먹고 2번 줄로 이동하여 7번째 동전까지 2번 줄에서 4개의 동전을 먹은 후 다시 1번 줄로 이동하여 마지막 3개의 동전을 먹으면 9개의 동전을 먹으면서 동전을 최대로 먹을 수 있다.

입력

첫째 줄에 두 정수 T(1≤T≤1,000), K(1≤K≤30)가 주어진다. 다음 T개의 줄에는 동전의 위치가 1 또는 2로 주어진다.

출력

구름카가 먹을 수 있는 동전의 최대 개수를 출력한다.