Elevator

Time limit1sMemory limit1024 MB

Summary

Rusnė goes from floor 0 to floor N using the elevator for at most K segments; minimize the total height of the segments she climbs on foot.

Level: Easy3 of 10
Topics: Greedy, Sorting, Dynamic programming
Solved: No attempts yet

Problem

Rusnė lives on floor $N$ of a building and uses the building's elevator every day. One day, for the sake of her health, she decides she will ride the elevator for at most $K$ floor-segments. However, the segments between consecutive floors have different heights (measured by the number of stairs), and Rusnė is clever: she wants to climb as few stairs on foot as possible.

You are given the height of every segment in the building. Find the minimum number of stairs Rusnė must climb on foot if she may ride the elevator for at most $K$ segments. (Rusnė may enter and exit the elevator as many times as she likes.)

Input

The first line contains two integers $N$ and $K$ — the floor Rusnė lives on, and the maximum number of segments she will travel by elevator.

Each of the next $N$ lines contains one integer $a_i$ — the height, in stairs, of the segment between floor $i-1$ and floor $i$ (for $i$ from $1$ to $N$ ).

The floors of the building are numbered from $0$ to $N$ . Floor $0$ is at ground level, and the elevator can be called on every floor.

Output

Print one integer — the minimum number of stairs Rusnė must climb on foot to get home.

Constraints

$0 \le K < N \le 10000$
$1 \le a_i \le 1000$

Examples3

Example 1
Input
```
5 3
19
20
20
20
14
```
Expected output
```
33
```
Example 2
Input
```
3 0
5
3
8
```
Expected output
```
16
```
Example 3
Input
```
4 3
10
1
5
7
```
Expected output
```
1
```