Se le da un arreglo que contiene ~n~ números enteros positivos.

Tu tarea consiste en dividir el arreglo en ~k~ subarreglos de forma que la suma máxima en un subarreglo sea lo más pequeña posible.

Entrada

La primera línea de entrada contiene dos enteros ~n~ y ~k~: el tamaño del arreglo y el número de subarreglos en la división.

La siguiente línea contiene ~n~ enteros ~x_1,x_2,\ldots,x_n~: el contenido del arreglo.

Salida

Imprime un entero: la suma máxima en un subarreglo en la división óptima.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq k \leq n~
• ~1 \leq x_i \leq 10^9~

Ejemplo de Entrada

5 3
2 4 7 3 5

Ejemplo de Salida

8

Explicación: Una división óptima es ~[2,4],[7],[3,5]~ donde las sumas de los subarreglos son ~6,7,8~. La mayor suma es la última suma ~8~.