As vacas querem melhorar como atletas, então Bessie treina numa pista por exatamente $N$ $(1 \le N \le 10,000)$ minutos. A cada minuto escolhe correr ou descansar durante o minuto inteiro.

A distância final depende do «fator de cansaço», inicialmente 0. Correr no minuto $i$ dá exatamente $D_i$ $(1 \le D_i \le 1,000)$ de distância e aumenta o fator em 1, mas nunca pode superar $M$ $(1 \le M \le 500)$. Descansar reduz 1 por minuto. Só pode voltar a correr quando ele chegar a 0; então pode correr ou descansar.

Ao fim dos $N$ minutos o fator de Bessie deve ser exatamente 0, ou não restará energia para o restante do dia.

Encontre a máxima distância possível.

Entrada

Leia da entrada padrão.

• Linha 1: inteiros $N$ e $M$ separados por espaço.
• Linhas $2..N+1$: a linha $i+1$ contém apenas o inteiro $D_i$.

Saída

Escreva na saída padrão.

• Linha 1: um inteiro com a maior distância respeitando as condições.

Exemplos

Entrada 1

5 2
5
3
4
2
10

Saída 1

9

Nota

Bessie corre no primeiro minuto ($distance=5$), descansa no segundo, corre no terceiro ($distance=4$), descansa no quarto e quinto. Não pode correr no quinto, pois o fator final não seria 0.

Autor: Neal Wu, 2007