Stones Distribution

The Innopolis sports center has an amazingly well-equipped hi-tech sauna. However, because complex techniques were used to build it, people are not sure how to maintain it properly.

The sauna has $n - 1$ consecutive compartments. 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, so there are exactly $n$ stoves in total.

The $i$-th compartment has volume $k_i$. Each stove can hold from 0 to $v$ stones. Let $p_i$ be the number of stones in the $i$-th stove. Then the $i$-th compartment receives $k_i \cdot p_i \cdot p_{i + 1}$ units of heat.

The sports center has $s$ stones for the stoves. The management wants to minimize the sum of heat received by all compartments so that the rest of the building does not get heated, but every stone must be used because buying them was a waste otherwise. Help the management solve this problem.

The first line contains three integers $n$, $s$, and $v$: the number of stoves, the number of stones, and the stove capacity ($2 \le n \le 1000$, $1 \le v \le 10^5$, $s \le n \cdot v$).

The second line contains $n - 1$ integers $k_i$, the volume of the $i$-th compartment ($1 \le k_i \le 10^5$).

Print the minimum possible total heat received by all compartments.

The correct answer for the sample is achieved by putting four stones in the first and the last stove and two stones in the second. Then the heat in every compartment except the second is 0, and the heat in the second compartment is $8$.