Given a sequence $a_1, a_2, \ldots, a_n$ of $n$ numbers. The cost of a consecutive segment $l, r$ is the maximum value among $a_l,a_{l+1},...,a_r$. Divide the sequence into $k$ consecutive segments such that the total cost of the segments is minimized.
### Input
- The first line contains two positive integers $n, k.$
- The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n.$
### Output
- Print the result of the problem.
### Constraints
- $ 1 \le n \le 200000.$
- $1 \le a_1,a_2,...,a_n \le 10^6.$
- $1 \le k \le 500.$
### Example
Input
```
5 2
1 2 3 4 5
```
Output
```
6
```
