MOG
Spanish
|
English

Matcom Online Grader

Latin American Regional Contest - 2004

Ended

A - Land Division Tax

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

International Concrete Projects Company (ICPC) is a construction company which specializes in building houses for the high-end market. ICPC is planning a housing development for new homes around a lake. The houses will be built in lots of different sizes, but all lots will be on the lake shore. Additionally, every lot will have exactly two neighbors in the housing development: one to the left and one to the right.
ICPC owns the land around the lake and needs to divide it into lots according to the housing development plan. However, the County Council has a curious regulation regarding land tax, intended to discourage the creation of small lots:

  1. land can only be divided using a sequence of land divisions;
  2. a land division is an operation that divides one piece of land into two pieces of land; and
  3. for each land division, a land division tax must be paid.

Denoting by $A$ the area of the largest resulting part of the division, the value of the land division tax is $A \times F$, where $F$ is the division tax factor set yearly by the County Council. Note that due to (2), in order to divide a piece of land into $N$ lots, $N - 1$ land divisions must be performed, and therefore $N - 1$ payments must be made to the County Council.

For example, considering the figure above, if the division tax factor is $2.5$ and the first land division separates the lot of $500$ units of area from the other lots, the land division tax to be paid for this first division is $2.5 \times (300 + 200 + 100 + 100 + 100)$. If the next land division separates the lot of $300$ units together with its neighbor lot of 100 units, from the set of the remaining lots, an additional $2.5 \times (300 + 100)$ must be paid in taxes, and so on. Note also that some land divisions are not possible, due to (2). For example, after the first land division mentioned above, it is not possible to make a land division to separate the lot of $300$ units together with the lot of $200$ units from the remaining three lots, because more than two parts would result from that operation.

Given the areas of all lots around the lake and the current value of the division tax factor, you must write a program to determine the smallest total land division tax that should be paid to divide the land according to the housing development plan.

Input

The input contains several test cases. The first line of a test case contains an integer $N$ and a real $F$, indicating respectively the number of lots $(1 \leq N \leq 200)$ and the land division tax factor (with precision of two decimal digits, $0 \lt F \leq 5.00$). The second line of a test case contains $N$ integers $X_i$, representing the areas of contiguous lots in the development plan ($0 \lt X_i \leq 500$, for $1 \leq i \leq N$); furthermore, $X_k$ is neighbour to $X_{k+1}$ for $1 \leq k \leq N − 1$, and $X_N$ is neighbour to $X_1$ . The end of input is indicated by $N = F = 0$.

Output

For each test case in the input your program must produce a single line of output, containing the minimum total land division tax, as a real number with precision of two decimal digits.

Sample test(s)

Input
4 1.50 2 1 4 1 6 2.50 300 100 500 100 100 200 0 0
Output
13.50 4500.00