Failed ZNO

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

After a poor result on the ZNO, Zenyk was sent to the army. Marichka’s father was a regiment commander, so Zenyk became the head of the cadets.

So Zenyk was tasked with choosing \(k\) cadets out of \(n\). He decided that he needs to line up all the cadets in a row and perform the following action several times.

• Choose one of the remaining cadets.

• Then choose whether this cadet pushes out of the line all cadets to the right or to the left.

• Push out all cadets in the chosen direction. For each pushed-out cadet, a uniform price must be paid.

For each cadet in the initial line, Zenyk knows the price for one cadet pushed out by them. Zenyk has problems with mathematics, which is why he ended up in the army.

He asks you to calculate the minimum number of hryvnias he has to pay to get a line of exactly \(k\) cadets.

Input

The first line gives two integers \(n\) and \(k\) — the initial and final number of cadets in the line, respectively.

The second line gives \(n\) integers \(a_i\) — the number of hryvnias that need to be paid to the \(i\)-th cadet for one pushed-out cadet.

Output

In a single line, print an integer — the minimum number of hryvnias required for Zenyk to narrow the line to \(k\) cadets.

Constraints

\(1 \le k \le n \le 10^5\),

\(1 \le a_i \le 10^9\),

for 13 tests, an additional constraint \(n \le 1000\) holds.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 4 7 7 4 4 7 7	12

Input (stdin) сopy	Output (stdout) сopy
6 2 1 3 4 2 5 6	10

Notes

In the first test, the fourth cadet pushes out three cadets to the right, and Zenyk will pay \(3 \cdot a_4 = 3 \cdot 4 = 12\) UAH for this.

In the second test, the fourth cadet pushes out two cadets to the right, after which the second cadet also pushes out two cadets to the right. In total, Zenyk will pay \(2 \cdot a_4 + 2 \cdot a_2 = 2 \cdot 2 + 2 \cdot 3 = 10\) UAH.