# Chef at the Olympics Codechef October Long Challenge

## 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.

Note:

• 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.

Input Format

• 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.

Output Format

For each query, output on a single line the best possible rank of country 1.

Constraints

• 1≤T≤105
• 1≤N≤105
• 1≤Q≤105
• 0≤B,S,G≤5⋅108
• 0≤K≤1015
• 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``````

Explanation

• 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

``1``

Explanation

Test Case 1: The only way is to change one of the gold medals of country 2 to a silver or bronze medal.