Problem A
Souvenir
Source code: souvenir.c, souvenir.pas, souvenir.p, souvenir.cc, or souvenir.cpp
Sue and Pat are planning to make a trip to see the most essential parts of Sweden. 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 Pat and Sue 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. Sue and Pat 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 Swedish Krona left, if they could have bought more expensive souvenirs. Your task is for each route to figure out how much money Pat and Sue 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
Lidsträsk   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
Bråvalla    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
Granvik     and so on...
2
90
80
2            The number of places on first route
50          The amount of souvenir money
Kalvträsk   The first place on first route
1           The number of souvenirs in this place
5          The cost of first souvenir
Åsträsk
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, 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.

The translation was made by Andreas Nilsson on Mon Sep 28 07:21:00 MET DST 1997