(Challenge) Biased Committee

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
N contestants are participating in a competitive programming contest. Each participant has a unique id between 1 and N (both inclusive). There are M problems in the contest.
The organizing committee didn't announce the maximum number of points for each problem; we only know that after the contest, the ratio of the number of points gained by the participant with id i on problem j to the maximum number of points for problem j is equal to A_{ij}/1000000, for each valid pair i, j. The total score for each participant is the sum of points gained on all problems.
After the contest, participants are ranked according to the total score; in case of a tie, the participant with the highest id has the best (lowest) rank.
For each valid i, let's denote the rank of the participant with id i by R_{i}. An inversion in the standings is a pair i, j such that i < j and R_{i} > R_{j}.
The committee now wants to assign maximum scores to problems. However, they can't assign the scores arbitrarily. For each problem, you are given two numbers L and U denoting the lower and upper bound for the maximum score — the maximum score for this problem has to be an integer between L and U (both inclusive).
The committee wants to assign the maximum scores in such a way that the number of inversions in the final standings is minimized. (That is, the best situation is when the participant with id 1 is ranked first, participant 2 is ranked second and so on.)
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two spaceseparated integers N and M.
 M lines follow. For each valid i, the ith of these lines contains two spaceseparated integers L_{i} and U_{i} denoting the lower and upper bounds to the ith problem.
 N more lines follow. For each valid i, the ith of these lines contains M spaceseparated integers A_{i1}, A_{i2}, ..., A_{iM}.
Output
For each test case, print a single line containing M spaceseparated integers denoting the maximum scores for the problems.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 1,000
 1 ≤ M ≤ 1,000
 0 ≤ A_{ij} ≤ 1,000,000 for each valid i, j
 0 ≤ L_{i} ≤ U_{i} ≤ 1,000,000 for each valid i
Test Generation
Each input file will contain T = 5 test cases with the following constraints:
 first test case: N = 1000, M = 1000
 second test case: N = 1000, M = 200
 third test case: N = 1000, M = 50
 fourth test case: N = 1000, M = 20
 fifth test case: N = 1000, M = 10
The remaining parameters are selected in the following way:
 for each valid i, L_{i} is selected uniformly randomly between 0 and 1000000 (both inclusive)
 for each valid i, each U_{i} is selected uniformly randomly between L_{i} and 1000000 (both inclusive)
 for each valid i, each A_{ij} is selected uniformly randomly between 0 and 1000000 (both inclusive)
Scoring
Your score for each test case is equal to max(0,N * (N1)/ 4  inv) where inv is the number of inversions in the final standings produced by your solution. Your total score is the sum of scores for all test cases in all test files, you should try to maximize this score. The scores visible during the contest will be computed only on 4 files. The scores based on all test files will be revealed after the contest.
Example
Input: 1 3 3 1 10 1 10 1 10 1 5 6 2 4 5 7 4 2 Output: 4 6 8
Explanation
Example case 1: participant 1 will have total score equal to (1*4 + 5*6 + 6*8)/1000000 = 82/1000000, participant 2 will have total score equal to (2*4 + 4*6 + 5*8)/1000000 = 72/1000000, participant 3 will have score equal to (7*4 + 4*6 + 2*8)/1000000 = 68/1000000, so participants will be ranked in the standings by 1, 2, 3, which has 0 inversions
Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/BIAS 
Tags  challenge, feb18, inversions, kingofnumbers 
Date Added:  31012018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 