La cuerda de la cometa
Un matemático, un ingeniero y un economista se quedaron una tarde a cargo del hijo menor de un amigo común. Para intentar mantener al chico entretenido, decidieron ayudarle a fabricar una cometa.
Tras buscar por la casa, encontraron multitud de cordeles de diferentes longitudes y calidades. Por mucho que buscaron, sin embargo, les resultó imposible encontrar unas tijeras infantiles y prefirieron no utilizar las de la cocina.
Dedicaron un rato a medir todos los cordeles y apuntaron concienzudamente sus longitudes. El muchacho, que estaba muy espabilado para su corta edad, pensó en pasar un buen rato a costa de sus tíos adoptivos y les dijo que quería que su cometa tuviera una cuerda de una longitud especifica, y no admitiría ninguna otra. Al no tener tijeras, tendrían que dedicar gran parte de la tarde a intentar averiguar si podrían juntar varios de los cordeles encontrados para sumar exactamente la longitud pedida. Durante ese tiempo, planeaba, se iría a ver la tele, que era lo que realmente estaba deseando hacer.
El matemático se emocionó con el inesperado reto que aparecía ante a sus ojos. Es más, mostrando una euforia que los demás estaban lejos de compartir, gritó "¡Esto es muy interesante! De hecho me pregunto ¿de cuántas formas diferentes podríamos formar la cuerda de ese tamaño?".
Al ingeniero, que entendió inmediatamente las intenciones del pequeño diablillo, no le hizo gracia la propuesta. "No nos vengas con monsergas ni preguntas retóricas, que te conocemos." — refunfuñó — "Lo importante es buscar cómo hacerlo con el mínimo número de cordeles, para acabar de unirlos lo antes posible, que esta tarde hay partido."
"¡¿Pero es que aún no conocéis suficiente al padre del muchacho?!" — replicó inmediatamente el economista — "Da igual cuántos nudos necesitemos, y cuánto tardemos. Lo importante es que la cometa salga lo más barata posible, o no nos invitará a cervezas cuando vuelva." Y tenía razón; junto a cada cordel encontrado, todavía se podía ver la etiqueta con su precio.
Entrada
La entrada consta de una serie de casos de prueba. Para cada uno, aparece el número N (entre 1 y 1.000) de cordeles y la longitud L de la cuerda de la cometa a formar (entre 1 y 1.000). A continuación aparecen N líneas con la descripción de cada cordel: su longitud y su coste (todos ellos números entre 1 y 1.000).
Salida
Para cada caso de prueba, si es posible formar la cuerda deseada, se escribirá SI seguido de las respuestas a las preguntas del matemático, el ingeniero y el economista: número total de maneras de conseguir esa cuerda, mínimo número posible de cuerdas a utilizar, y mínimo coste necesario. Se garantiza que ninguno de esos números será mayor de 1018. Si no es posible formar la cuerda se escribirá, simplemente, NO.
En todos los casos, se debe suponer que la realización de cada nudo no supone reducción alguna en la longitud de los cordeles. Además, ten en cuenta que al contar el número de formas de conseguir la cuerda, el orden en el que se unan los cordeles es irrelevante; si para conseguir la cuerda final se tienen que utilizar varios cordeles, todos los modos de ordenarlos entre sí se considerarán una única forma.
Entrada de ejemplo
4 50 10 25 20 15 30 40 40 75 3 10 1 30 2 60 3 90 3 2 1 10 1 10 1 10
Salida de ejemplo
SI 2 2 55 NO SI 3 2 20