Problema número 701

Haciendo la compra

Tiempo máximo: 1,000-4,000 sMemoria máxima: 24576 KiB
Refrigerador de un supermercado con productos lácteos

Cuando va al supermercado a comprar, Hu L. Mal siempre tiene mucho cuidado con los productos que coge. No soporta que las cosas le caduquen en la nevera de modo que antes de llevarse algo (botellas de leche, huevos, o lo que sea) rebusca en los estantes para coger los que tienen fecha de caducidad más tardía. Pero ¡no siempre es fácil! Los reponedores del supermercado tienden a colocar delante las unidades que caducan antes, para que los clientes se lleven esas primero. Al final nuestra amiga Hu termina con medio cuerpo dentro de los refrigeradores rebuscando los yogures que más durarán en casa.

Los reponedores la han visto varias veces en este ejercicio extravagante y han decidido contraatacar. Ahora colocan las cosas revueltas, poniendo, por ejemplo, dos yogures que caducan el mismo día al lado de otros 4 que caducan varios días después, y detrás otros cuantos que caducan antes. Hu insiste en llevarse a casa las unidades por orden inverso de fecha de caducidad y con esta medida su tiempo de compra se está alargando ostensiblemente.

Entrada

El programa deberá procesar múltiples casos de prueba. Cada uno comienza con el número de unidades de un determinado producto que se quieren comprar (entre 1 y 107). A continuación, se indica cuántos "bloques" de unidades hay de ese producto en el supermercado con la misma fecha de caducidad (al menos 1 y como mucho 300.000).

Por cada uno de esos bloques aparece una línea con dos números. El primero indica de cuántas unidades está compuesto el conjunto (como mucho 100), y el segundo el número de días que faltan para que caduque (menos de 109). Ten en cuenta que los reponedores colocan los productos de forma caótica intencionadamente, y podría haber varios conjuntos con la misma fecha de caducidad.

La entrada termina con un 0.

Salida

Por cada caso de prueba se escribirá cuántos días faltan para que caduque la unidad que antes lo hace de aquellas que se han comprado.

Entrada de ejemplo

8
5
3 3
2 2
2 1
2 5
2 3
0

Salida de ejemplo

2