Farmer John es un extraordinario experto contable y se da cuenta de que puede quedarse sin dinero para la granja. Calculó y anotó exactamente los gastos ($1 \le money_{i} \le 10,000$) de cada uno de los próximos $N$ días ($1 \le N \le 100,000$).

FJ crea un presupuesto para exactamente $M$ períodos fiscales sucesivos ($1 \le M \le N$), llamados «fajomonths». Cada uno contiene uno o más días consecutivos, y cada día pertenece exactamente a uno.

Quiere organizar los períodos para minimizar los gastos del período más costoso y determinar su límite mensual.

Entrada

Línea 1: dos enteros separados por un espacio: $N$ y $M$. Líneas $2\ldots N+1$: la línea $i+1$ da los dólares que Farmer John gasta el día $i$.

Salida

Línea 1: el menor límite mensual posible para Farmer John.

Ejemplos

Entrada 1

7 5
100
400
300
100
500
101
400

Salida 1

500

Nota

Si los primeros dos días forman un mes, el tercero y cuarto otro, y los últimos tres cada uno su propio mes, gasta como máximo 500 dólares por mes. Cualquier otra distribución requiere un límite mensual mínimo mayor.

Fuente del problema: USACO, marzo de 2007.