Stones Distribution

There is an amazingly equipped hi-tech sauna in Innopolis sport center. However, due to complex techniques were used while building it people are not sure how to maintain it properly.

There are n - 1 consecutive compartments in the sauna. Between each pair of adjacent compartments, there is a stove. There are two more stoves: one connected only to the first compartment, and one connected only to the last, which makes exactly n stoves.

The i-th compartment has volume k[i]. Each stove can have from 0 to v stones. Let p[i] be the number of stones in thei-th stove, then the i-th compartment receives k[i] * p[i] * p[i+1] units of heat.

There are s stove stones in sport center. Sport center management wants to minimize the sum of heat received by all compartments, so the rest of the building would not be heated up, but all stones have to be used as it is a waste to buy them otherwise. Help them solve the problem.

Input

The first line contains three integers n, s and v (2 ≤ n ≤ 1000, 1 ≤ v ≤ 10^5, s ≤ n * v) - number of stoves, number of stones and stove capacity, respectively.

The second line contains n - 1 integers k[i] - the volume of the i-th compartment (1 ≤ k[i] ≤ 10^5).

Output

Print the minimum possible total heat received by all compartments.

Examples

Note

In the example the correct answer is achieved if we put four stones into the first and the fourth stove, and two stones into the second. Then the heat in all compartments, except the first, will be zero, and in the first - eight.