Se le proporciona una matriz que contiene n números enteros positivos. Su tarea es dividir la matriz en k submatrices de modo que la suma máxima en una submatriz sea lo más pequeña posible.

Entrada

La primera línea de entrada contiene dos números enteros n y k: el tamaño de la matriz y el número de submatrices en la división. La siguiente línea contiene n números enteros x_1,x_2,...,x_n: el contenido de la matriz.

Salida

Imprima un número entero: la suma máxima en una submatriz en la división óptima. Restricciones

1 <= n <= 200,000 1 <= k <= n 1 <= x_i <= 1,000,000,000

Ejemplos

Entrada:

5 3
2 4 7 3 5

Salida:

8

Explicación: Una división óptima es [2,4],[7],[3,5] donde las sumas de las submatrices son 6,7,8. La suma más grande es la última suma 8.