감시 초소

최근 적군의 동향이 심상치 않다는 보고를 받은 지휘관은 접경 지역에 감시초소를 설치하여 모든 접경 지역을 완벽히 감시하고자 한다. 접경 지역은 1번 지역부터 $N$번 지역까지 $N$개가 있으며, 거리 1 간격으로 왼쪽부터 오른쪽까지 일렬로 나열되어 있다. 단, 접경 지역의 길이는 0이라고 가정한다. 지역 $i$에 감시초소를 설치하려면 $c_i$의 비용을 부담해야 하며, 각 접경 지역에는 감시초소를 하나만 설치할 수 있다.

각 감시초소에는 최소 한 명의 병사가 분대장으로 배치되어야 하며, 분대장은 항상 감시초소가 설치된 지역을 감시한다. 감시초소에 병사를 추가로 배치하면 더 많은 지역을 감시할 수 있다. 거리가 $x$만큼 떨어진 지역을 하나 더 감시하려면 $x+1$명의 병사를 추가로 배치해야 한다. 감시초소들이 감시하는 영역이 겹치면 혼동이 생기므로, 지휘관은 각 감시초소가 연속된 지역만 감시하도록 지시했다. 다만 각 감시초소에는 최대 $P$명까지만 배치할 수 있다.

모든 접경 지역을 감시하는 데 필요한 최소 비용을 구하여라.

첫째 줄에 접경 지역의 개수 $N$과 각 감시초소에 배치할 수 있는 최대 인원수 $P$가 공백으로 구분된 정수로 주어진다.

둘째 줄에는 $1$번 지역부터 $N$번 지역까지 감시초소를 건설하는 데 드는 비용 $c_i$가 공백으로 구분된 정수로 주어진다.

모든 접경 지역을 감시하는 데 필요한 최소 비용을 출력한다.

• $1 \leq P \leq N \leq 100000$
• $1 \leq c_i \leq 10^9$