Migrated from Lutece 429 Print Article

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Zero has an old printer that doesn't work well sometimes. As it is antique, he still likes to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero uses a cost to evaluate this degree.

One day Zero wants to print an article which has $N$ words, and each word i has a cost $C_i$ to be printed. Also, Zero know that print $k$ words in one line will cost

$M$ is a const number. Now Zero wants to know the minimum cost in order to arrange the article perfectly.

Input

There are many test cases. For each test case, There are two numbers $N$ and $M$ in the first line ($0\leq n\leq 500000$, $0\leq m\leq 1000$). Then, there are $N$ numbers in the next lines. Input are terminated by EOF.

Output

A single number, meaning the minimum cost to print the article.

Samples

5 5
5 9 5 7 5

230

Resources

2010 ACM-ICPC MU Training - Host by HIT