Expert Programmer
Your dream is to become an expert programmer one day and you are practicing day and night for that dream to come true. Right now you are practicing for the next big programming contest and you want to be prepared for that. All the plans are laid out - you have a list of categories for programming problems (e.g. DP, Graph, String etc.) and for each category you collected a list of problems to solve. Time is short though, it is unlikely that you can become expert in all categories before the contest.
So, the plan is to target a subset of the categories and become “expert” in those categories. Also, you want to choose the categories such that you can maximize your expertise in a number of categories.
Let’s say, there are K categories of problems in total and for each category you need to earn some point, Ei, to gain expertise in that category. In each category there is a number of problems , Ni, that you can practice. Each problem takes some amount of time, L, (in minutes) to solve and you can earn some amount of points, P, by solving each problem. The values for L and P can be different for each problem.
The contest is coming soon and you only have D minutes left to practice. Within that time in what is maximum number of categories of problems can you gain expertise in?
Input
Input starts with an integer, T, denoting the number of test cases. The remaining of the input consist of information of each of the test cases. There is an empty line before each test case including the first test case.
Each test case starts with an integer, K, denoting the number of categories and an integer, D, denoting number of minutes left to practice.
Next line contains K integers, Ni, denoting number of problems in i-th category.
Next line contains K integers, Ei, denoting number of points required to be expert in the i-th category.
Each of the remaining lines within the test case has contains a pair of integers, L and P, denoting how long it takes to solve the problem and how many points you gain by solving the problem. The first N1 lines contain description of problems for first category sequentially. Next N2 lines contain description of problems for second category, and so on.
Constraints
Output
For each test print a single line with the indices of the categories that you can achieve expertise is. Use 1-based indexing for the categories. If more than one solution is possible print the lexicographically smallest indices for the categories. If you can not gain expertise on any of the category, just print “Better luck next time” on a single line without the quotes.
Sample
| Input | Output |
|---|---|
3 3 30 1 1 2 10 20 40 10 15 30 50 20 45 30 65 3 40 1 1 2 10 20 50 10 15 30 50 20 45 30 65 2 20 2 2 100 100 10 15 30 50 20 45 30 65 | 1 3 1 2 Better luck next time |
