Problema número 661

Los tesoros de la tumba de Tutankamón

Tiempo máximo: 2,000 sMemoria máxima: 4096 KiB
Contenido de la antecámara de la tumba de Tutankamón

Cuando en 1922 Howard Carter encontró, tras años de búsqueda, la tumba de Tutankamón, tuvo claro que no había sido saqueada con anterioridad, como ocurría habitualmente. En el ajuar funerario había, junto al ataúd de oro macizo y la máscara funeraria, carros de guerra, trompetas, arcos, sandalias y hasta ropa interior de lino.

El valor de aquellos tesoros era incalculable por lo que su recuperación tuvo que ser realizada con mucha delicadeza. Por miedo a que, tras su descubrimiento, algún ladrón aprovechara para saquear la tumba, se realizó un inventario de los objetos y se les asignó un valor y peso estimado. Luego, se fueron extrayendo de la tumba los objetos empezando por los de mayor valor. En caso de empate, se empezaba por los de menor peso. Si había dos objetos con el mismo valor y peso estimado, se extraía primero el que apareciera antes en el inventario.

Entrada

Cada caso de prueba comienza con un número 1 ≤ n ≤ 100 indicando la cantidad de objetos encontrados en la tumba de Tutankamón. A continuación aparecen n líneas, con el inventario de las piezas.

Cada objeto se describe con su nombre (una única palabra de menos de 10 letras del alfabeto inglés en minúscula), su valor histórico y su peso. Se garantiza que no hay objetos con el mismo nombre, y que tanto el valor como el peso son números entre 1 y 1.000.

La entrada termina con un caso sin objetos, que no debe ser procesado.

Salida

Por cada caso de prueba el programa escribirá, en una línea, los nombres de los objetos, separados por espacio, en el orden en el que deben ser extraídos de la tumba.

Entrada de ejemplo

5
flecha 5 1
sandalias 10 2
sarcofago 1000 1000
mascara 1000 10
arco 10 2
0

Salida de ejemplo

mascara sarcofago sandalias arco flecha