A la captura del Doctor Muerte
Los 4 Fantásticos han dado con el escondrijo del Doctor Muerte en la lejana Latveria y van a intentar capturarlo para que pague por sus numerosos crímenes. El Doctor Muerte, con el fin de protegerse, se ha rodeado de sus sirvientes a modo de escudos humanos.
Reed Richards, líder de Los 4 Fantásticos, posee muchas armas (de un solo uso) para enfrentarse al Doctor Muerte, pero quiere utilizarlas con sabiduría: cada arma ocasiona un daño distinto a inocentes y a villanos.
Ante la situación actual, Reed Richards seleccionará siempre primero las armas que causen un menor daño a inocentes y, en caso de empate, aquellas que causen mayor daño a villanos. Si hay dos armas iguales, se usará primero la que vaya antes en la lista.
Sabiendo el daño que hay que inflingir al Doctor Muerte para vencerle, la forma en la que se elegirán las armas y recordando que solo pueden usarse una vez, es el momento de elegir las armas a utilizar.
Entrada
La entrada estará compuesta de múltiples casos de prueba, cada uno ocupando varias líneas.
Un caso de prueba comienza con dos números 1 ≤ V ≤ 10.000 con la vitalidad del Doctor Muerte y 1 ≤ N ≤ 1.000 con el número de armas disponibles.
A continuación aparecerán N líneas. Cada una indica las características de un arma con dos números (entre 0 y 10.000) con el daño que hace a inocentes y a villanos, respectivamente.
La entrada termina con un cero.
Salida
Por cada caso de prueba se escribirá una línea indicando la sucesión de armas escogidas hasta la derrota del Doctor Muerte. Las armas se identifican por su posición en la lista de la entrada (números entre 1 y N), y aparecerán separadas por un espacio. Ten en cuenta que el modo de elegir las armas ¡podría no ser el que menos daño total haga a inocentes!
Si es imposible derrotar al Doctor Muerte se escribirá "MUERTE ESCAPA".
Entrada de ejemplo
100 4 9 100 8 90 2 11 8 89 100 1 10 99 0
Salida de ejemplo
3 2 MUERTE ESCAPA