¡El Granjero Juan ha olvidado completamente cuántas vacas tiene! También le da vergüenza ir a sus campos a contar sus vacas, pues no quiere que las vacas se den cuenta de su laguna mental. En vez de eso, él decide contar sus vacas secretamente plantando micrófonos en los campos en las cuales las vacas tienden a reunirse, pensando que él puede determinar el número de vacas a partir del volumen total de todo el mugido que él oye.

Los ~N~ campos de GJ ~(1 \leq N \leq 100)~ están distribuidos en una línea a lo largo de un camino recto largo. Cada campo puede contener varias clases de vacas: GJ posee ~B~ razas de vacas ~(1 \leq B \leq 20)~ y una vaca de la raza ~i~ muge con un volumen de ~V(i)~ ~(1 \leq V(i) \leq 100)~. Aún más, hay un fuerte viento soplando a lo largo de la carretera, el cual lleva el sonido del mugido en una dirección: si el volumen de mugido en algún campo es ~X~, entonces en el siguiente campo contribuirá ~X-1~ al volumen total de mugido (y ~X-2~ en el campo después de ese,etc.)

Dado el volumen de mugido que GJ registra en cada campo, por favor, calcule la cantidad mínima de vacas que GJ podría tener.

El volumen que GJ registra en cualquier campo es a lo más 100,000.

Entrada

• Línea 1: Los enteros ~N~ y ~B~.
• Líneas 2..1+B: La línea ~i+1~ contiene el entero ~V(i)~.
• Líneas 2+B..1+B+N: La línea ~1+B+i~ contiene el volumen total de todo el mugido en el campo ~i~.

Ejemplo de Entrada

5 2
5
7
0
17
16
20
19

Detalles de la Entrada: GJ posee 5 campos, con volúmenes de mugido ~0, 17, 16, 20, 19~. Hay dos razas de vacas; las primera muge a un volumen de 5 y la otra a un volumen de 7.

Salida

En una sola línea escribir la mínima cantidad de vacas que posee GJ o -1 si no hay ninguna configuración de vacas consistente con la entrada.

Ejemplo de Salida

4

Detalles de la Salida: Hay dos vacas de raza #1 y una vaca de raza #2 en el campo 2, y hay otra vaca de raza #1 en el campo 4.