Farmer John é um extraordinário mestre da contabilidade e percebe que pode ficar sem dinheiro para a fazenda. Calculou e registrou exatamente os gastos ($1 \le money_{i} \le 10,000$) de cada um dos próximos $N$ dias ($1 \le N \le 100,000$).

FJ quer um orçamento para exatamente $M$ períodos fiscais sucessivos ($1 \le M \le N$), chamados «fajomonths». Cada um contém um ou mais dias consecutivos, e cada dia pertence exatamente a um período.

Quer organizar os períodos para minimizar os gastos daquele que gasta mais, determinando o limite mensal.

Entrada

Linha 1: dois inteiros separados por espaço: $N$ e $M$. Linhas $2\ldots N+1$: a linha $i+1$ dá os dólares que Farmer John gasta no dia $i$.

Saída

Linha 1: o menor limite mensal possível para Farmer John.

Exemplos

Entrada 1

7 5
100
400
300
100
500
101
400

Saída 1

500

Nota

Se os primeiros dois dias forem um mês, o terceiro e quarto outro, e os últimos três cada um seu próprio mês, gasta no máximo 500 dólares por mês. Qualquer outra distribuição dá um limite mensal mínimo maior.

Fonte do problema: USACO, março de 2007.