Stones Distribution#8646
There is an amazingly equipped hi-tech sauna in the city sport center. However, due to the complex techniques 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 stoves.
The -th compartment has volume k_i. Each stove can have from to stones. Let p_i be the number of stones in the -th stove, then the -th compartment receives k_i \cdot p_i \cdot p_{i+1} units of heat.
There are stove stones in the 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.
The first line contains three integers , and (2 \le n \le 1000, 1 \le v \le 10^5, s \le n \cdot v) - number of stoves, number of stones and stove capacity, respectively.
The second line contains n - 1 integers k_i - the volume of the -th compartment (1 \le k_i \le 10^5).
Print the minimum possible total heat received by all compartments.
Example 1
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.