건강한 식사

면접 대비

시간 제한2초메모리 제한1024 MB

요약

빵이 k일 뒤에 상할 때, 매일 아침 빵 2개를 먹기 위해 필요한 최소 비용과 날짜별 구매 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 슬라이딩 윈도우, 그리디
정답자: 아직 제출이 없습니다

문제

볼로자는 학생이라 건강한 식사가 필요하다. 그는 몇 년째 매일 아침 빵 두 개와 주스를 먹는다.

빵은 보관한 지 $k$ 일이 지나면 상한다. 그래서 볼로자는 매일 아침 가게에 가서 신선한 빵을 산다. 빵 가격은 환율 변동 때문에 매일 바뀐다. 볼로자는 가게 주인에게 앞으로 $m$ 일 동안의 빵 가격을 알아냈다. 이제 그는 이 $m$ 일 동안의 아침 식사를 위한 구매 계획을 세우려고 한다. 재정 위기와 타고난 인색함 때문에 볼로자는 빵을 사는 데 돈을 가능한 한 적게 쓰고 싶어 한다. 그를 도와 보자.

입력

첫 줄에 두 정수 $m$ 과 $k$ 가 주어진다. $m$ 은 계획을 세울 날의 수이고, $k$ 는 빵의 보관 기간이다( $1 \le m, k \le 100\,000$ ). 둘째 줄에는 $m$ 개의 자연수 $c_i$ 가 주어진다. $c_i$ 는 $i$ 일의 빵 가격이다( $1 \le c_i \le 1\,000\,000$ ).

출력

첫 줄에 볼로자가 필요한 금액 $C$ 를 출력한다. 둘째 줄에는 $m$ 개의 정수 $d_i$ 를 출력한다. $d_i$ 는 $i$ 일에 사는 빵의 개수이다.

예제2

예제 1
입력
```
2 1
1 2
```
예상 출력
```
6
2 2
```
예제 2
입력
```
3 2
3 1 2
```
예상 출력
```
10
2 4 0
```