Repartiendo horchata
Organizar las fallas en Valencia da mucho calor. Afortunadamente, la Junta Central Fallera obsequia a los artistas falleros con horchata de chufa al acabar el trabajo. La horchata es una bebida refrescante compuesta por agua, azúcar y chufas, un tubérculo comestible producido por una planta herbácea. A veces se añaden otros ingredientes para potenciar el sabor, como canela y piel de limón.
En el puesto donde la Junta Central Fallera va a repartir la horchata se está formando una enorme cola de gente deseando hidratarse, cada uno con su botella vacía a la espera de ser llenada. A la vista de la longitud, la organización teme que la cantidad de horchata disponible no vaya a llegar para todos y ha decidido repartirla en función de las prioridades.
Ha categorizado a cada una de las personas que está esperando con un número que indica el trabajo realizado en la organización. Un número más alto indica mayor trabajo y, por tanto, mayor prioridad a la hora de recibir el refresco. También ha mirado el tamaño de las botellas de cada uno. La horchata se repartirá primero a los que más han trabajado y, en caso de empate, a los que menos horchata pidan.
Entrada
Cada caso de prueba comienza con una línea con dos números. El primero, 1 ≤ h ≤ 107, indica la cantidad de horchata disponible para repartir. El segundo, 1 ≤ n ≤ 1.000, dice cuánta gente hay esperando para llenar sus botellas.
A continuación vienen n líneas, cada una describiendo las características de una de las personas a la espera. Cada línea contiene dos números, 1 ≤ t ≤ 100.000, indicando la cantidad de trabajo realizado por esa persona, y 1 ≤ c ≤ 10.000, con la cantidad de horchata que espera recibir en su botella.
La entrada termina con dos ceros que no deben procesarse.
Salida
Por cada caso de prueba el programa escribirá dos números. El primero indica cuánta gente recibe horchata y el segundo cuánta horchata sobra tras el reparto. La gente recibe horchata por orden de prioridad, empezando por aquellos que más han trabajado y, en caso de empate, por los que menos horchata piden. Cuando no queda suficiente horchata para satisfacer a la siguiente persona que le tocaría, se deja de repatir sin darle nada.
Entrada de ejemplo
10 2 6 4 4 7 15 3 5 8 6 10 5 5 8 2 5 5 10 10 0 0
Salida de ejemplo
1 6 2 0 0 8