위버워치

강의도 끝났고, 과제도 다 했고, 짜증나는 조교들도 네 코딩 프로젝트에 대해 더 이상 트집 잡을 게 없다. 이제 게임을 할 시간이다! 미루기의 달인인 너는 늘 그렇듯 절묘한 타이밍을 잡았다. Cold Weather Entertainment가 경쟁형 1인칭 비디오 게임 위버워치를 막 출시한 것이다!

안타깝게도 너는 이런 게임을 잘하지 못한다. 하지만 위버워치는 단순히 실력만 요구하는 게임이 아니다. 위버워치에서는 궁극기를 쓰면 버튼 하나로 시야에 들어온 모든 적을 처치할 수 있다. 이 공격의 단점은 사용하려면 시간이 지나면서 충전해야 한다는 것이다. 완전히 충전되면 원하는 때에 언제든 쓸 수 있다. 사용한 뒤에는 곧바로 다시 충전을 시작한다.

이 사실을 알게 된 너는 곧바로 전략을 세운다.

• 적들에게서 숨어 궁극기가 충전되기를 기다린다.
• 적절한 순간을 기다린다.
• 궁극기로 시야에 들어온 모든 적을 처치한다.
• 반복한다.

게임이 끝난 뒤 팀원들이 큰 기여를 했다며 축하해 준다. 하지만 너는 궁금해진다. 최적으로 타이밍을 맞췄다면 몇 명의 적을 처치할 수 있었을까?

게임은 n개의 시간 구간에 걸쳐 관찰된다. 궁극기는 처음에는 충전되어 있지 않으며 충전하는 데 m개의 시간 구간이 필요하다. 따라서 궁극기를 처음 사용할 수 있는 시점은 (m+1)번째 시간 구간이다. i번째 시간 구간에서 궁극기를 사용하면 곧바로 다시 충전을 시작해 (i + m)번째 시간 구간에 발사할 준비가 된다.

입력은 다음과 같다.

• 두 정수 n과 m이 주어지는 한 줄. 여기서

  • n (1 ≤ n ≤ 300 000)은 게임의 길이이고,
  • m (1 ≤ m ≤ 10)은 궁극기를 충전하는 데 필요한 시간 구간의 수이다.

• 시간 구간마다 시야에 들어온 적의 수 xi (0 ≤ xi ≤ 32)를 순서대로 나타내는 n개의 정수가 주어지는 한 줄.

처치할 수 있는 적의 최대 수를 출력한다.