Souvenir

Janez and Micka are planning to make a trip to see the most essential parts of Slovenia. They have been planning the trip very precisely. They know which places to visit so they know exactly how much the trip will cost. Since Janez and Micka really want to make sure they will remember all the places they have been to, they want to have a souvenir from every place they visit to keep for the rest of their lives. Janez and Micka study business and they really want their budget to meet perfectly. They will not be happy if they could have bought souvenirs from all places and still have one single tolar left, if they could have bought more expensive souvenirs. Your task is for each route to figure out how much money Janez and Micka will have left in their souvenir budget if they buy something in each place, and spend as much of the budget as possible in total.

Sample of the input file:
2 The number of routs
3 The number of places on first route
100 The amount of souvenir money
Ljubljana The first place on first route
2 The number of souvenirs in this place
9 The cost of first souvenir
15 The cost of second souvenir
Celje The second place on first route
3 The number of souvenirs in this place
13 The cost of first souvenir
17 The cost of second souvenir
11 The cost of third souvenir
Grad The third place on first route
2 The number of souvenirs in this place
90 The cost of first souvenir
80 The cost of second souvenir
2 The number of places on second route
50 The amount of souvenir money
Maribor The first place on second route
1 The number of souvenirs in this place
5 The cost of first souvenir
Murska Sobota
3
27
43
50

Resulting output file:
0 The amount of money left of the souvenir money on first route
2 The amount of money left of the souvenir money on second route

Note! The input file are not indented this way (also without comments), the output file should not be indented either.

Limits: There will be no more than 20 routes, 20 places on each route and no more than 20 souvenirs in each place.