The Lalalandia's Christmas is coming! Only $$N$$ days are left and Jambo wants to buy all his friends a present. There are $$N$$ presents that his friends want and Jambo, because he is a very small elephant, cannot buy and carry more than $$K$$ presents at any day. Every present in $$j$$th day costs $$a_i * j$$ for every $$1 \le j \le N$$. Can you help Jambo determine the minimum amount of money needed to buy all presents and make his friends happy?
The first line consists of integers $$N$$ - the number of days and the number of presents Jambo wants to buy, and $$K$$ - the number of presents Jambo can carry. The second line contains n integers $$a_1, a_2, ..., a_N$$ — the cost of the $$i$$th present.
The first line should contain the single integer - answer to the problem.
$$1 \le N \le 10^5$$
$$1 \le K \le N$$
$$1 \le a_i \le 10^9$$
Since $$K$$ equals to $$1$$, the optimal solution is $$3 * 1 + 2 * 2 + 1 * 3 = 10$$.