MOG Round #19Ended |
Fitiño, el hermano de Fito, está jugando con un juego de bloques que le compro su hermano mayor. Los bloques de este juego tienen una forma algo extraña como la que se muestra en la figura:
La figura que se muestra es un bloque 3x2, como se puede ver este tiene tres dientes salientes en la partes superior izquierda y tres dientes entrantes en la parte inferior izquierda y a partir del medio de la pieza hay dos dientes salientes en la parte superior y dos dientes en la parte inferior. Es fácil ver que un bloque de este tipo
NxM
puede ir sobre otro bloque de igual tipo
NxM
, pero también puede ir sobre un bloque que
PxQ
donde
N >=P y M>=Q
. Por lo que nuestra tarea consiste dado un conjunto de bloques saber la cantidad máxima que se puede apilar.
La entrada posee varios casos de prueba, la primera línea de cada caso de prueba es un entero
N (1<=N<=10000)
que representa la cantidad de bloques, luego en
N
líneas hay dos números,
P
y
Q
separados por un espacio que representan un bloque
PxQ (1<=P, Q<=100)
. La entrada termina cuando
N=0.
Por cada caso de prueba se imprime la mayor cantidad de bloques que se pueden apilar. Cuando se termina la salida se imprime un “
*
”.