Surveillance Posts

Time limit1.5sMemory limit1024 MB

Summary

Split border zones 1 to N into disjoint contiguous ranges, each with one post and at most P soldiers, and find the minimum total build cost.

Level: Medium6 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

The commander has received reports that enemy movements have turned ominous, and wants to place surveillance posts along the border so that every border zone is fully watched. There are $N$ border zones, numbered 1 through $N$ , lined up from left to right with a distance of 1 between neighboring zones. The length of each zone is 0. Building a post in zone $i$ costs $c_i$ , and each zone can hold at most one post.

Each post must have at least one soldier assigned as its squad leader, and the squad leader always watches the zone where the post is built. More soldiers can be assigned to a post so that it watches more zones. To watch one more zone at distance $x$ away, $x+1$ additional soldiers must be assigned. If the watch areas of two posts overlap, the zones can be confused, so the commander ordered that each post watch only a contiguous range of zones. However, each post can hold at most $P$ soldiers.

Find the minimum total cost needed to watch all border zones.

Input

The first line contains the number of border zones $N$ and the maximum number of soldiers $P$ per post, separated by a space.

The second line contains the build costs $c_i$ for zones $1$ through $N$ , separated by spaces.

Output

Print the minimum total cost needed to watch all border zones.

Constraints

$1 \leq P \leq N \leq 100000$
$1 \leq c_i \leq 10^9$

Examples2

Example 1
Input
```
5 5
10 8 3 6 1
```
Expected output
```
9
```
Example 2
Input
```
6 6
9 8 1 10 3 99
```
Expected output
```
4
```