감시 초소

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

각각의 감시초소에는 최소한 한 명의 병사가 분대장으로 배치되어야 하며, 분대장은 항상 감시초소가 설치되어 있는 지역을 감시한다. 감시초소에 병사를 추가로 배치하여 더 많은 지역을 감시할 수 있는데, 거리가 $x$만큼 떨어진 지역 하나를 추가로 감시하기 위해선 $x+1$명의 병사를 추가로 배치해야 한다. 또한, 감시초소들이 감시하는 영역이 교차하면 혼동이 생길 것을 우려한 지휘관은, 반드시 각각의 감시초소에서 연속적인 지역들만을 감시하도록 지시했다.

그러나, 건설할 수 있는 감시초소의 크기가 작아 각각의 감시초소에는 최대 $P$명의 병사까지만 배치할 수 있다고 한다. 지휘관을 위해, 모든 접경 지역을 감시하기 위해 필요한 최소 비용을 구하여라.

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

두 번째 줄에 $i$번 지역에 감시초소를 건설하는 비용 $c_i$가 공백으로 구분되어 정수로 주어진다.

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

• $1\leq P\leq N\leq 100\,000$
• $1\leq c_i\leq 10^9$