Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está estudiando ordenación y se le ha ocurrido un problema bien interesante.

Se tiene un array de enteros de tamaño n y se definen dos funciones sobre este array cuyas implementaciones en C# son:

int Sum( int [] a, int p, int k)

{

int result = 0;

for ( int i = p; i <= k; i++)

result += a[i];

return result;

}

int T( int [] a)

{

int result = int .MinValue;

for ( int i = 0; i < a.Length; i++)

for ( int j = i; j < a.Length; j++)

result = Math .Max(result, Sum(a, i, j));

return result;

}

En este array se pueden hacer varios intercambios (swap) entre cualquier dos elementos de índices i , j (0<=i<j<=n-1) . ¿Cuál es el máximo valor de T(a) que se puede obtener si a lo sumo se pueden hacer Q intercambios en el array a?

Input

La primera línea de la entrada contiene dos números separados por un espacio n y Q (1<=n<=1000; 1<=Q<=10) . La segunda línea contiene n enteros a[0], a[1], a[2],..., a[n-1] separados por un espacio (-1000 <= a[i] <= 1000) que representa el array a.

Output

Se debe imprimir en una sola línea el valor máximo que puede obtener T(a) con a lo sumo Q intercambios.

Sample test(s)