There are n water deposits in a line.
They are so huge that they can be considered to have infinite capacity.
Initially, each deposit i has ℓ_{i} liters in it.
You have a pump that you can use
to transfer water from any deposit i to any adjacent deposit (i − 1 or i + 1).
Each use of the pump to transfer water between two deposits has cost p + ℓ,
where p is a constant cost to connect two adjacent deposits,
and ℓ is the number of liters transferred.
Your goal is to minimize the cost
to equally distribute the water among all the deposits.

Input

Input consists of several cases,
each with n and p,
followed by ℓ_{1}, …, ℓ_{n}.
You can assume 1 ≤ n ≤ 10^{5},
0 ≤ p ≤ 10^{9},
0 ≤ ℓ_{i} ≤ 10^{9},
and that the sum of all ℓ_{i}’s is a multiple of n.

Output

For each case, print the minimum cost to equally distribute the water among all the deposits.

Public test cases

**Input**

4 42 5 5 5 5 1 8 100 7 100 10 30 14 6 50 15 15 8 10 0 0 0 0 0 0 1000000000 1000000000

**Output**

0 0 551 6000000070

Information

- Author
- Jordi Cortadella
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Quinzè Concurs de Programació de la UPC - Semifinal
- Date
- 2017-06-29