Árvore de Natal
Por Julio Cesar Ceron, beecrowd 
Brazil
Por Julio Cesar Ceron, beecrowd Brazil
Com a chegada do clima natalino muitas famílias ao redor do mundo decoram suas casas, colocam luzes constroem suas próprias árvores de natal, colocando os mais váriados enfeites decorativos sempre com muita criatividade. Na família Enilno Egduj, descendetes de Italianos, sempre muito organizados e perfeccionistas criaram uma tradição onde todo o ano alguém fica responsável por enfeitar a árvore de natal. Neste ano o filho mais novo da família Rolien Enilno Egduj, ficou encarregado de fazer a decoração, e para isso precisava comprar os enfeites para a árvore. Para quem não conhece Rolien, ele é um menino muito perfeccionista, tão perfeccionista que decidiu fazer um programa para auxilia-lo na sua tarefa.
Para enfeitar a árvore estavam disponíveis no mercado onde Rolien foi procurar enfeites natalinos, vários pacotes com uma quantidade X de enfeites e em cada pacote o seu respectivo peso em gramas. Baseando-se nessas informações Rolien estipulou que cada galho pudesse suporta uma quantidade K em gramas.
Com isso ele precisava encontrar qual a melhor opção entre os pacotes, ou seja, quais pacotes ele deve levar que combinados possuam o maior número de enfeites e que o galho ao qual ele vai enfeitar consiga suportar suportar o peso dos enfeites.
A primeira linha de entrada possui um inteiro G para os galhos da árvore, e também representando o numero de casos de teste, a segunda linha de entrada possui um inteiro P (1 < P < 100) que indica o número de pacotes, a próxima linha possui um inteiro W (1 < W < 1000) que indica a capacidade de peso que o galho da árvore suporta. As próximas P linhas indicam o número de enfeites em cadas pacote E(1 < E ≤ 300) e o peso de cada pacote PC (1 ≤ PC ≤ W).
A saída devera apresentar o número total de enfeites para cada galho.
| Exemplo de Entrada | Exemplo de Saída |
|
3 |
Galho 1:
Galho 2:
Galho 3: |