# Practice on Toph

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

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

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, **E _{i}**, to gain expertise in that category. In each category there is a number of problems , N

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 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, **N _{i}**, denoting number of problems in i-th category.
Next line contains

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 **N _{1}** lines contain description of problems for first category sequentially. Next

1 <= T <= 50 1 <= K <= 20 1 <= D <= 10^9 1 <= N_{i}<= 100 1 <= E_{i}<= 10000 1 <= L <= 100 1 <= P <= 100

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.

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 |

71% Solution Ratio

avivillaEarliest,

Emruz_HossainFastest, 1103052.5s

mahbubcsejuLightest, 131 kB

m1n2o3Shortest, 1600B

Login to submit