sumarum
Djurica has found n cards. Each card contains an integer written on it. For the given array of cards Djurica wants to calculate the value of f(A) where:
f(A) = Σ(A(k + 1) - A(k)), k = 1 .. n - 1. He can get rid of at most K cards. When he gets rid of m cards where m<=k he gets a new array for which he calculates f(A). Djurica wants to know what is the greatest value of f(A) so that the number of cards that are removed from the array is less or equal to K. HELP HIM DO IT!
InputFirst line contains numbers n(2<=n<=500000) and K(0<=K<=n-2). Second line contains n integers where the i-th integer Ai(-1000000<=Ai<=1000000) is the number written on the i-th card.
OutputFirst line of the output should contain an integer representing the greatest value of f(A) Djurica can get.
Input
Output
11 4
1 7 2 5 3 8 2 3 6 5 5Output
5Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.