Deadpool doesn't like arrays. Arrays remind him of Ajax. Being the violent guy that he is, whenever he sees an array all he can think of is splitting the array array into pieces ( exactly what he would like to do to Ajax ).

For some weird reasons , he wants you to solve the following problem for him. And when Deadpool asks you to do something , you don't have no choice but to do what he says.

You are given an array Arr with N elements . You have to split the array into disjoint parts, and choose K parts from those disjoint parts such that the sum of all the elements in all these K parts is maximum possible.

Note : Each of the K parts is actually a sub array as the array can only be split into continuous segments.

INPUT

First line of input contains 2 integers N and K, denoting the size of array and the number of segments the array has to be split into.

Next line contains N integers denoting the elements Arr[i] of the array.

OUTPUT

Print the maximum possible sum when from the array k segments are chosen out of the split segments.

CONSTRAINTS

1<=N<=2000

1<=K<=N<=2000

-10⁹ <= Arr[i] <= 10⁹