La línea marítima "Titanic S.A.", cuya flota consta de un único buque, se ocupa del transporte de mercancías desde el puerto nuevo de Villabajo de Arriba allende los mares. Cada uno de los productos tiene un volumen (por motivos de conservación, las mercancías van siempre embaladas en cajas) y un precio de venta. Ante la convocatoria inminente de una huelga de estibadores, la línea decide efectuar un viaje extraordinario llenando el buque de manera que la mercancía que transporte sea lo más valiosa posible. Se pide construir un programa que, dada la información de las mercancías (volumen, precio y unidades disponibles), determine cuáles deben transportarse en el buque sin desbordar su capacidad (que será una información adicional sumistrada al programa). En caso que existan diversas combinaciones óptimas de mercancía con respecto al precio, se elegira aquélla que ocupe menos volumen; en este caso, sí puede suponerse que existe una única solución óptima al problema.

Entrada

Residente en el fichero de caracteres "BUQU.DAT":

Línea 1: número N de tipos de mercancías, mediante uno o dos caracteres que representan un número entero entre 1 y 99.
Línea 2: capacidad del buque, mediante uno, dos, tres o cuatro caracteres que representan un número entero entre 1 y 9999.
Líneas de la 3 a la N+2: cada una de las líneas tiene el formato:

    mercancía volumen coste unidades

donde mercancía es una palabra formada exclusivamente por letras minúsculas (y sin signos de puntuación, es decir, ni acentos ni similares) de a lo sumo 20 letras, y los otros tres componentes son enteros representados mediante un número de dígitos que oscila entre 1 y 5 (es decir, el entero más grande representable es el 99999). Los componentes de la línea están separados por un único carácter blanco, y no existen blancos ni otro tipo de caracteres al principio o final de línea.

Salida

A guardar en el fichero de caracteres "BUQU.OUT":

Línea 1: un par de enteros representados mediante dígitos de la manera habitual, que indican el coste total de la carga transportada y el volumen. Ambos valores están separados por un único carácter blanco, y no existen blancos ni otro tipo de caracteres al principio o final de línea.
Líneas siguientes: cada una de ellas contiene un par:

    mercancía unidades

que dice cuantas unidades de una mercancía dada aparecen en la carga transportada. La mercancía debe haber aparecido como tal en el fichero de entrada. Las unidades se representan mediante dígitos de la manera habitual. Ambos valores están separados por un único carácter blanco, y no existen blancos ni otro tipo de caracteres al principio o final de línea. No deben aparecer mercancías con cero unidades transportadas. Las líneas deben estar ordenadas alfabéticamente según el nombre de la mercancía; no deben aparecer mercancías repetidas.

Ejemplo de entrada

5
2000
patatas 350 2 7
judias 400 5 4
guisantes 1000 12 4
fresones 1100 17 3
arroz 600 8 1

Ejemplo de salida

27 1900
fresones 1
judias 2