Здоровое питание

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

요약

m일 동안 매일 빵 두 개를 먹어야 하고 i일에 산 빵은 k일까지 쓸 수 있다. 총비용을 최소로 하는 날짜별 구매량을 구한다.

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

문제

Как и всем студентам, Володе необходимо здоровое питание. Каждый день вот уже несколько лет Володя ест на завтрак две булочки и сок.

К несчастью для Володи, булочки не вечны и портятся через $k$ дней хранения, поэтому каждое утро он ходит в магазин и покупает в нем свежие булочки. Однако цены на булочки из-за колебаний курсов валют постоянно меняются.

Благодаря своей хитрости Володе удалось выяснить у продавца магазина цены булочек на ближайшие $m$ дней. Теперь Володя хочет составить план закупок завтраков, которыми он будет питаться в эти $m$ дней.

В связи с финансовым кризисом и природной жадностью Володя хочет потратить на булочки наименьшее возможное количество денег.

Помогите ему в этом!

입력

В первой строке входного файла находятся два числа: $m$ --- число дней на которые надо разработать план закупок, и $k$ --- срок хранения булочек ( $1 \le m, k \le 100\\,000$ ). Во второй строке дано $m$ натуральных чисел $c\_i$ --- цена булочки в $i$ -ый день ( $1 \le c\_i \le 1\\,000\\,000$ ).

출력

В первой строке входного файла выведите число $C$ --- количество денег, необходимое Володе. Во второй строке выведите $m$ чисел $d\_i$ --- число булочек, покупаемых Володей в $i$ -ый день.

예제2

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