J. Janitor's Cart
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The organizers of the programming championship have printed the problem statements in several university offices. The university janitor must collect the statements and bring them to the staircase.

A staircase is at one end of a straight corridor with $$$n$$$ offices. Office $$$i$$$ is located $$$i$$$ meters along the corridor from the staircase and contains $$$a_i$$$ printed statements.

You need to move all the statements to the staircase using a cart that can carry at most $$$c$$$ statements at a time. Each trip starts at the staircase with an empty cart and ends at the staircase, where all collected statements are unloaded.

During a trip, you may collect statements from several offices. Statements from the same office may be transported on different trips.

Find the minimum total distance traveled by the cart.

Input

The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le c \le 10^9$$$): the number of offices and the capacity of the cart.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^6$$$): the numbers of statements in the offices.

Output

Print one integer: the minimum total distance, in meters, needed to move all the statements to the staircase.

Examples
Input
3 3
2 0 2
Output
8
Input
2 2
0 5
Output
12
Input
4 10
0 0 0 0
Output
0
Note

In the first example, one trip collects two statements from office $$$3$$$ and one from office $$$1$$$. Its length is $$$6$$$ meters. Another trip collects the remaining statement from office $$$1$$$ and has length $$$2$$$ meters. The total distance is $$$8$$$ meters.

In the second example, office $$$2$$$ has five statements. Three trips of length $$$4$$$ meters each are needed, so the answer is $$$12$$$.

In the third example, there are no statements, so no trips are needed.