## Table of Contents

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

**Subtasks**

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

*October Long Challenge 2021*

*October Long Challenge 2021*