Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Expert Programmer

Limits: 10s, 1.0 GB

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

1 <= T <= 50
1 <= K <= 20
1 <= D <= 10^9
1 <= Ni <= 100
1 <= Ei <= 10000
1 <= L <= 100
1 <= P <= 100

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.

Samples

InputOutput
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

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial