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.
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.
Print one integer: the minimum total distance, in meters, needed to move all the statements to the staircase.
3 32 0 2
8
2 20 5
12
4 100 0 0 0
0
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.
