See Russian Translation

A few months ago, it was discovered that there exists a gate that opens into another world!

In the new world, there are some primitive civilizations. Therefore, your country has decided to set up a communication network on the straight road between the gate and the foreign capital city. To accomplish this, the country has K available communications towers and hired you to make a plan for the placement of some or all of these towers.

There are N possible locations on the straight road that you can set up a communications tower at. If we number these positions with the natural numbers from 1 to N, we find that the distance between position i and position i + 1 is a constant 1 unit over all i. Therefore, the distance between two towers i and j is equal to |i - j|.

Before a tower is set up, the land must first be prepared. You will hire local workers to prepare the land, but you must pay them in local currency. The current exchange rate of your currency to local currency is 1024 : 1. The cost to prepare the land at the location i is given by Ai, which is guaranteed to be a positive multiple of 1024.

Additionally, it is necessary to build towers at the location of the gate and at the location of the foreign capital. These two locations are locations 1 and N, respectively.

You have devised a formula to calculate the overall cost of the operation. A feasible plan is a set S (2 ≤ |S| ≤ K) of locations that you plan to build towers on. Assume Si denotes the i^th element of the set S, and that Si < Si+1 for all i. The overall cost for a set S is

K × K × (AS1 + AS2 + ... + AS|S|) + (S2 - S1)^2 + (S3 - S2)^2 + ... + (S|S| - S|S|-1)^2.

This formula accounts for the cost of preparing the land to build towers on as well as the communication strength on all points on the road. Intuitively, building too few towers will reduce the cost of land preparation, but it will also reduce the communication strength, resulting in a higher overall cost.

You should formulate a feasible plan to minimize the overall cost, and output this minimum value.

Input Format:
The first line of input will contain N and K, the number of locations and the number of towers at your disposal, respectively.
The second line of input will contain N integers, A1 to AN.

Output Format:
The first and only line of output should contain the minimum overall cost for a feasible plan.

Constraints:
For all subtasks,
2 ≤ K ≤ N
1024 ≤ Ai ≤ 2^20
Ai will be divisible by 1024.
[Subtask 1 - 8%]
2 ≤ N ≤ 15
[Subtask 2 - 4%]
2 ≤ N ≤ 30
[Subtask 3 - 25%]
2 ≤ N ≤ 300
[Subtask 4 - 13%]
2 ≤ N ≤ 10^5
Additionally, Ai = 1024 for all i.
[Subtask 5 - 50%]
2 ≤ N ≤ 10^5

SAMPLE INPUT
4 3
3072 65536 65536 2048

SAMPLE OUTPUT
46089

Explanation

The optimal solution is to build 2 towers at locations 1 and 4, with overall cost 3 × 3 × (3072 + 2048) + 3^2 = 46089.

见题面

见题面