URI Online Judge | 2026

Christmas Tree

By Julio Cesar Ceron, URI Online Judge BR Brazil

Timelimit: 2

With the arrival of Christmas atmosphere many families around the world decorate their homes, they put lights build their own Christmas tree, putting the most varied decorations always smartly. Family Enilno Egduj, descendetes of Italians, always very organized and perfectionist created a tradition where every year someone is responsible for decorate the Christmas tree. This year the youngest child of Rolien Enilno Egduj family, was in charge of making the decor, and it needed to buy the ornaments for the tree. For those unfamiliar Rolien, he is a very perfectionist boy, such a perfectionist that descidiu make a program to assist you in your task.

To decorate the tree were available in the market where Rolien was looking for Christmas decorations, several packages with X amount of ornaments and each package its respective weight in grams. Based on this information Rolien stipulated that each branch could support a quantity K in grams.

With that I needed to find what the best option among the packages, ie packages which it should take that combined have the largest number of decorations and the branch to which it will spruce can withstand withstand the weight of ornaments.

Input

The first input line has an integer  G  to the tree branches, and also representing the number of test cases, the second inlet line has an integer  P (1 < P < 100) indicating the number of packets, the next an entire line has  W (1 < < 1000), which indicates the weight capacity of the tree branch supports. The next  P  lines indicate the number of ornaments on fied package  E(1 < E ≤ 300) and the weight of each package PC (1 ≤ PC ≤ W).

Output

The output must submit the total number of decorations for each branch. Print a blank line after the full trappings of each branch.

Input Sample Output Sample

3
3
30
30 15
10 12
12 18
4
32
12 10
15 8
18 19
22 23
5
40
22 12
35 30
10 16
9 7
17 10

Galho 1:
Numero total de enfeites: 40


Galho 2:
Numero total de enfeites: 37


Galho 3:
Numero total de enfeites: 52