Water deposits P41867

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 $\ell_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 + \ell$, where $p$ is a constant cost to connect two adjacent deposits, and $\ell$ 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 $\ell_1, \dots, \ell_n$. You can assume $1 \le n \le 10^5$, $0 \le p \le 10^9$, $0 \le \ell_i \le 10^9$, and that the sum of all $\ell_i$’s is a multiple of $n$.

Output

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