Time Limit: 2 sec
Memory Limit: 32 MB
Lithuanian migration department has announced that approximately 90 thousand Lithuanians will have emigrated by the end of 2010. This is many times more than any other European country and if no measures will be taken the whole population will be subject to extinction.
The department is investigating possible ways of attracting Lithuanians back to their country, and most importantly reduce existing emigration. The next step of the investigation includes consolidation of data received from Lithuanian embassies across the world, in order to identify the regions where Lithuanians have migrated: United Kingdom, Norway, Ireland among others.
To identify what measures are best the following poll was arranged in some of the countries. People where asked to choose what government activity can bring them home. Each activity i has associated cost X in litas. Total cost to implement the activity consists of fixed and variable costs. Fixed cost is the same for all countries. Variable cost depends on the number of emigrants in that particular country. You also know that activity i has efficiency E, given in percent, meaning that E% emigrants will be attracted back home. Efficiency can be different for different countries. Each activity is always implemented to all people in a country, but only some will return back home to Lithuania.
Given that no effective activity compensating emigration has been found so far the government has decided to diversify the activities and implement each activity at most in 1 country, to mitigate the risk of missing potentially undervalued activities. However, different activities can be implemented in different countries. You are asked to find the number of Lithuanians that can be attracted back home according to the poll results.
On the first line of input you are given a number of tests T (T ≤ 100). Each test starts with a line containing 3 positive integers separated by a space character: K (K ≤ 5) — number of activities, N (N ≤ 10) — number of countries, M (M ≤ 1000) — money that government can spend on activities in millions of litas. Then data about activities follow containing K lines. Each line describes an activity contains 1 upper-case latin alphabet letter (activity name) and 2 positive integers: Cp — fixed cost in thousands of litas, Cv variable cost per person in litas. First line of data for each country specifies the number of activities Ki ≤ K applicable to that country, and Pi (Pi ≤ 106) — the number of emigrants in that country. Ki lines follow each specifying the activity index, and an integer number specifying efficiency of the activity in percent of country’s population. When calculating number of people attracted by activity in a country round to the nearest integer, and if needed half up.
For each test case print a line containing the maximum number of Lithuanians that can be attracted back home.
1 2 1 100 A 1000 2 B 500 1 2 1000000 A 50% B 25%
500000