# Water deposits P41867

Statement

thehtml

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 ≤ 105, 0 ≤ p ≤ 109, 0 ≤ ℓi ≤ 109, 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