URI Online Judge | 1767

Santa Claus Bag

By Neilor Tonin, URI Online Judge BR Brazil

Timelimit: 2

Santa Claus are ready to start his trips to deliver Christmas presents. The SBC (Brazilian Society of Carriers) determined that the maximum weight of each bag with gifts can be up to 50 kg, preserving the elves, who are Santa Claus helpers of any injury in the back when are carrying the sleigh and also so that Santa Claus does not hurt himself when is delivering the gifts.

Once all the toys are grouped into packages, your task is help with a program that join the maximum possible of toys within the weight limit of 50 kgs. In the sequence, Y-URI which is the chief of elfs, will put this bag in the sled and this way Noel can go on with his trip.


The input contain many test cases. The first line contains an integer N that is the number of test cases or the number of Santa Claus trips. Each trip begin with an integer Pac (1 < Pac < 100) that indicates the amount of packages available to this trip. The next Pac lines will contain two integer numbers qt (1 ≤ qt < 300) and weight (1 ≤ weight ≤ 50) that are respectively the amount of toys and the weight of each package, separated by a blank line.


For each test case, your program should print three lines, with corresponding message in portuguese, as shown below, followed by a blank line. The first one must contain the amount of toys that Y-URI will load up the sleigh. The second line contains the total weight of toys. The last line will contain the amount of packets left over for a future trip. In the second test case below, for example, 106 toys were selected for the trip, grouped into packs with 24, 2, 3, 4, 5 and 8 kg for a total of 46 pounds.

For the greater amount of toy selected, will have just one amount of weight or left packages possible.

Input Sample Output Sample

6 17
21 23
72 24
143 2
1 17
11 23
22 24
13 2
23 3
24 4
9 5
8 6
7 7
15 8

236 brinquedos
Peso: 49 kg
sobra(m) 1 pacote(s)

106 brinquedos
Peso: 46 kg
sobra(m) 4 pacote(s)