Ir al contenido (saltar navegación)

Pintando la pared

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Hombre con un rodillo en la mano, mirando una pared parcialmente pintada y rascándose la cabeza

Para pintar una pared de su habitación, Jorge ha decidido seguir el siguiente procedimiento: moja el rodillo en pintura, lo coloca horizontalmente en un punto arbitrario de la pared, y lo hace rodar hasta llegar al suelo. Después de un rato pintando de este modo, la zona pintada de la pared es un conjunto de rectángulos solapados que llegan hasta el suelo de la habitación, y Jorge se pregunta cuál será su área total.

Entrada

La entrada está formada por distintos casos de prueba, y cada caso de prueba consiste en una única línea con varios números.

El primer número de cada linea es un entero A, (1 ≤ A ≤ 5.000) que indica la anchura del rodillo. El siguiente número es un entero N (1 ≤ N ≤ 1.000) que indica el número de veces que se pasa el rodillo por la pared. A continuación aparecen N parejas de números enteros (xiyi), i=1,...,N. Cada pareja indica las coordenadas en la pared en las que se sitúa el lado izquierdo del rodillo en cada una de las pasadas. La coordenada (0, 0) corresponde a la esquina inferior izquierda de la pared. Se cumplen las condiciones 0 ≤ xi ≤ 2.000.000 y 1 ≤ yi ≤ 200.000.

El final de la entrada se indica con una línea con un único 0 que no se debe procesar.

Salida

Para cada caso de prueba, se escribirá una línea con un número entero igual al área de la región pintada de la pared.

Entrada de ejemplo

10 2 10 20 15 10
10 3 10 5 13 20 12 10
0

Salida de ejemplo

250
220