Dividir o array com a soma mínima

Dado n inteiros e um inteiro k, é necessário dividir o array em k partes contíguas de modo que a soma máxima de cada subarray seja a menor possível.

Entrada

A primeira linha de entrada contém dois inteiros n (1 ≤ n ≤ ) e k (1 ≤ k ≤ n).

A linha seguinte contém inteiros separados por espaço ( ≤ ≤ ).

Saída

O programa deve imprimir a menor possível soma máxima de um subarray.

Exemplos

Explicação

1. [1 2 3] [6 2] ⇒ a soma máxima do subarray é 6 + 2 = 8

2. [1 2] [10] [3 2] ⇒ a soma máxima do subarray é 10