Las vacas quieren ser mejores atletas, así que Bessie se ejercita en una pista durante exactamente $N$ $(1 \le N \le 10,000)$ minutos. Cada minuto elige correr o descansar todo el minuto.

La distancia final depende del «factor de agotamiento», inicialmente 0. Al correr en el minuto $i$ recorre exactamente $D_i$ $(1 \le D_i \le 1,000)$ y el factor aumenta 1, pero nunca puede superar $M$ $(1 \le M \le 500)$. Al descansar disminuye 1 por minuto. No puede volver a correr hasta llegar a 0; entonces puede correr o descansar.

Al acabar los $N$ minutos debe ser exactamente 0, o Bessie no tendrá suficiente energía para el resto del día.

Halla la máxima distancia que puede correr.

Entrada

Lee de la entrada estándar.

• Línea 1: enteros $N$ y $M$ separados por espacio.
• Líneas $2..N+1$: la línea $i+1$ tiene un solo entero $D_i$.

Salida

Escribe en la salida estándar.

• Línea 1: un entero con la mayor distancia que satisface las condiciones.

Ejemplos

Entrada 1

5 2
5
3
4
2
10

Salida 1

9

Nota

Bessie corre el primer minuto ($distance=5$), descansa el segundo, corre el tercero ($distance=4$), descansa el cuarto y quinto. No puede correr el quinto porque no acabaría con factor 0.

Autor: Neal Wu, 2007