T.E. Lawrence, popularized by the movie Lawrence of Arabia, was a British officer during World War I. He is best known for disrupting the railroads of the Ottoman Empire.

For this problem, the railroad of concern runs uninterrupted without branches through several outposts.

P ----- P ----- P ----- P

Each outpost has a value. The strategic value of a group of connected outposts is the sum of the pairwise products of the outposts. A single outpost a has no strategic value; two connected outposts a and b have strategic value a*b; three connected outputs a, b, and c have stategic value a*b + a*c + b*c; and so on.

The total stategic value of the railroad is the sum of the strategic values of these connected groups

Lawrence can attack and destroy a certain number of railroad segments. His goal is to reduce the strategic value of the railroad as much as possible.

For example, consider the following railroad

4 ----- 5 ----- 1 ----- 2

The stategic value is 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2, or 49.

Suppose Lawrence has one attack, which is marked by an x.

1. He could attack the left segment.

   4   x   5 ----- 1 ----- 2

   The left group has no value, and the right group has value 5*1 + 5*2 + 1*2, for a total of 17.
2. Or he could attack the middle segment.

   4 ----- 5   x   1 ----- 2

   The left group has value 4*5, and the right group has value 1*2, for a total of 22.
3. Or he could attack the right segment.

   4 ----- 5 ----- 1   x   2

   The left group has value 4*5 + 4*1 + 5*1, and the right group has no value, for a total of 29.

In this case, it would be best for Lawrence to attack the left segment.

Input

The first line is the number of outposts, 0 < P <= 500.

The second line is the number of railroad segments Lawrence can destroy, 0 <= N < P.

The third line is the space-separated values of the S outposts. Each value is an integer from 0 to 20, inclusive.

Output

The minimum possible stategic value of the railroad after Lawrence's attack.

Sample

Input 1
4
1
4 5 1 2

Output 1
17

Input 2
4
2
4 5 1 2

Output 2
2