Healthy Diet

Interview

Time limit2sMemory limit1024 MB

Summary

Given m daily bun prices and a shelf life of k days, find the minimum cost of 2 buns per morning and how many buns to buy each day.

Level: Medium5 of 10
Topics: Sliding window, Greedy
Solved: No attempts yet

Problem

Volodya is a student, so he needs a healthy diet. For several years, he has eaten two buns and a glass of juice every morning for breakfast.

The buns spoil after $k$ days of storage, so every morning he goes to the store and buys fresh buns. The bun prices change every day because of currency fluctuations. Volodya found out the bun prices at the store for the next $m$ days. Now he wants to plan his breakfast purchases for these $m$ days. Because of the financial crisis and his natural stinginess, Volodya wants to spend as little money on buns as possible. Help him!

Input

The first line contains two integers $m$ and $k$ : the number of days to plan for and the storage life of the buns ( $1 \le m, k \le 100\,000$ ). The second line contains $m$ positive integers $c_i$ , the price of a bun on day $i$ ( $1 \le c_i \le 1\,000\,000$ ).

Output

The first line contains the amount of money $C$ that Volodya needs. The second line contains $m$ integers $d_i$ , the number of buns Volodya buys on day $i$ .

Examples2

Example 1
Input
```
2 1
1 2
```
Expected output
```
6
2 2
```
Example 2
Input
```
3 2
3 1 2
```
Expected output
```
10
2 4 0
```