October Long Challenge Chef at the Olympics

October Long Challenge Chef at the Olympics

The Chef is at the Olympics. You are given the medal tally of NN of the participating countries.

You are also given QQ queries, each represented by a single integer KK. For each such query, you need to find the best possible rank country 11 can achieve if you are allowed to take any KK medals (possibly of different countries) and change their color.


  • Countries are ranked lexicographically in order of their gold, silver, and bronze medals. If countries ii and jj have the same number of gold, silver, and bronze medals, then country ii is considered to be ahead of country jj if and only if i<ji<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 TT denoting the number of test cases. Then the test cases follow.
  • The first line of each test case consists of two space separated integers NN and QQ denoting the number of countries and the number of queries.
  • NN lines follow. The ii-th line consists of three separated integers GG, SS, and BB indicating that the ii-th country has won GG gold medals, SS silver medals, and BB bronze medals.
  • QQ lines follow. The ii-th line line consists of a single integer KK describing the ii-th query.

Output Format

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


  • 1≤T≤1051≤T≤105
  • 1≤N≤1051≤N≤105
  • 1≤Q≤1051≤Q≤105
  • 0≤B,S,G≤5⋅1080≤B,S,G≤5⋅108
  • 0≤K≤10150≤K≤1015
  • Sum of NN over all testcases is atmost 5⋅1055⋅105.
  • Sum of QQ over all testcases is atmost 5⋅1055⋅105.


Subtask 1 (100 points): Original constraints

Sample Input 1 

5 3
1 3 5
2 3 5
1 2 4
2 2 5
3 2 5

Sample Output 1 



Test Case 11: We will change one bronze medal of country 11 to a gold medal.

Test Case 22: We will change two bronze medals of country 11 to gold medals.

Test Case 33: We will change three silver medals of country 11 to gold medals.

Sample Input 2 

2 1
2 0 0
2 1 0

Sample Output 2 



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


Solution will be updated soon mean while keep trying..

October Long Challenge 2021

Leave a Comment