Tulip Bouquets

Task

Anna really likes tulips. She has $N$ tulips in her garden, numbered from $0$ to $N-1$. The beautiness of tulip $i$ is $T_i$.
She wants to create $K$ (non-empty) bouquets from the tulips. To do that, she starts to walk from the first tulip towards the last.
At each flower, she can either

• insert it into the current bouquet, or
• finish the current bouquet and start a new one. The current tulip is added to the new bouquet.

The beautiness of a bouquet is the minimum of the beautinesses of the tulips in it.
She wants to maximize the sum of the beautinesses of the $K$ bouquets by partitioning the tulips optimally.
Your task is to calculate this maximum value!

Input data

The input file consists of:

• a line containing integers $N$, $K$.
• a line containing the $N$ integers $T_{0}, \, \ldots, \, T_{N-1}$.

Output data

The output file must contain a single line with an integer $M$, the maximum total beautiness of the bouquets.

Constraints and clarifications

• $1 \le K \le N \le 100 \ 000$.
• $1 \le N \cdot K \le 5 \cdot 10^7$.
• $0 \le T_i \le 10^9$ for each $i=0\ldots N-1$.

Example 1

stdin

5 2
3 4 1 5 2

stdout

4

Explanation

In the first sample case $3\: 4\: |\: 1\: 5\: 2$ is an optimal way to distribute the flowers into $2$ bouquets.
The total beautiness is $3+1=4$.

Example 2

stdin

6 4
4 2 6 1 3 5

stdout

14

Explanation

In the second sample case $4\: 2\: |\: 6\: |\: 1\: 3\: |\: 5$ is an optimal way to distribute the flowers into $4$ bouquets.
The total beautiness is $2+6+1+5=14$.