Score : 600 points
We will create an artwork by painting black some squares in a white square grid with 10^9 rows and N columns.
The current plan is as follows: for the i-th column from the left, we will paint the H_i bottommost squares and will not paint the other squares in that column.
Before starting to work, you can choose at most K columns (possibly zero) and change the values of H_i for these columns to any integers of your choice between 0 and 10^9 (inclusive).
Different values can be chosen for different columns.
Then, you will create the modified artwork by repeating the following operation:
Find the minimum number of times you need to perform this operation.
Input is given from Standard Input in the following format:
N K H_1 H_2 ... H_N
Print the minimum number of operations required.
4 1 2 3 4 1
3
For example, by changing the value of H_3 to 2, you can create the modified artwork by the following three operations:
6 2 8 6 9 1 2 1
7
10 0 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
4999999996