Chef at the Olympics Solution
The Chef is at the Olympics. You are given the medal tally of N of the participating countries. You are also given Q queries, each represented by a single integer K. For each such query, you need to find the best possible rank country 1 can achieve if you are allowed to take any K medals (possibly of different countries) and change their color.
- Countries are ranked lexicographically in order of their gold, silver, and bronze medals. If countries i and j have the same number of gold, silver, and bronze medals, then country i is considered to be ahead of country j if and only if i<j. There are no ties in the rank list.
- Since the input-output is large, prefer using fast input-output methods.
- The first line contains T denoting the number of test cases. Then the test cases follow.
- The first line of each test case consists of two space separated integers N and Q denoting the number of countries and the number of queries.
- N lines follow. The i-th line consists of three separated integers G, S, and B indicating that the i-th country has won G gold medals, S silver medals, and B bronze medals.
- Q lines follow. The i-th line line consists of a single integer K describing the i-th query.
For each query, output on a single line the best possible rank of country 1.
- Sum of N over all testcases is at most 5⋅105.
- Sum of Q over all testcases is at most 5⋅105.
Subtask 1 (100 points): Original constraints
Sample Input 1
1 5 3 1 3 5 2 3 5 1 2 4 2 2 5 3 2 5 1 2 3
Sample Output 1
3 1 1
- Test Case 1: We will change one bronze medal of country 1 to a gold medal.
- Test Case 2: We will change two bronze medals of country 1 to gold medals.
- Test Case 3: We will change three silver medals of country 1 to gold medals.
Sample Input 2
1 2 1 2 0 0 2 1 0 1
Sample Output 2
Test Case 1: The only way is to change one of the gold medals of country 2 to a silver or bronze medal.