Teamwork#10401
For his favorite holiday, Farmer John wants to send presents to his friends. Since he is not very good at wrapping presents, he wants to enlist the help of his cows. As you might expect, the cows are not much better at wrapping presents themselves — a lesson Farmer John is about to learn the hard way.
Farmer John's cows are standing in a row, conveniently numbered from to in order. Cow has a present-wrapping skill level of s_i. These skill levels may vary considerably, so FJ decides to split his cows into teams. A team may consist of any group of at most consecutive cows, and no cow may belong to more than one team. Since the cows learn from each other, the skill level of every cow in a team can be raised to the skill level of the most skilled cow in that team.
Help FJ determine the maximum possible sum of skill levels he can achieve by forming the teams optimally.
The first line contains two integers and k~(1 \le n \le 10^4, 1 \le k \le 10^3). Each of the next lines contains the skill level of one cow, in the order in which the cows are standing. Each skill level is a positive integer not exceeding 10^5.
Print one integer — the maximum possible sum of skill levels FJ can achieve by splitting the cows into teams of consecutive cows.
In this example, the optimal solution is to group the first cows and the last cows, leaving the middle cow in a team by herself (recall that teams of fewer than cows are allowed). As a result, the skill levels of the cows become , , , , , , , which sum to .
Example 1