Logombia is a beautiful country located in the middle of the continent, surrounded by two seas and constituted as a democratic state. Now it’s time for the Logombians to choose their president, but the organization of the event is a little late ... that’s why they hired you to automatize the process. As you well know, the right wing always postulate a candidate, like the left wing does too. On the other hand, in Logombia exists a lot of independent political factions, of which at least one postulate a candidate. With this conditions, there will be at least 3 candidates in the first round of elections. If a candidate gets a percentage greater than or equal to 50.1% will be elected as a president, in the other case the two candidates with the most votes will pass to a second round. Because of its mountainous geographical condition, there aren’t a very effective way to communicate different states in the country. Each state makes the election in a defined day and when they have finished counting votes they send a report to the capital where it indicate the amount of people who vote and the percentage of votes that each candidate gets in the state. It is guaranteed that the number of votes for each candidate in each state is an integer number. Losers candidates will organize protest marches and will blame the capitalism or Communism ac- cording to the case, but that is not your problem. Your work is process all the reports sent by each state and define who is the new president and how many votes he obtains, or well, who are the two candidates that dispute the second round and the amount of votes each one gets. Input Input begins with a non negative integer, the number of test cases. Each case begins with a line containing 2 integers numbers A and B, the number of candidates and the number of states (3 ≤ A ≤ 500 and 1 ≤ B ≤ 1000), followed by B lines, each one with A real numbers separated by a blank space, representing the vote’s percentage Pi (0.0 ≤ Pi ≤ 100.0) of each candidate from P1 to PA and an integer number V (1 ≤ V ≤ 108), the amount of voters in that state. The sum of the percentages in each state is equal to 100. Output For each case, if there is no need to a second round, print a single line containing the number of the candidate who wins and the number of votes he gets, otherwise, prints two lines with the number and the amount of votes of each candidate who passed to the second round, print first the candidate with most votes. In a case of a tie print the results order by the id of the candidates. Print a blank line between consecutive test cases. Sample Input 3 43 25.0 25.0 25.0 25.0 4500 26.0 24.0 27.0 23.0 9000 10.0 10.0 10.0 70.0 1000 31 51.0 24.0 25.0 1000 22 0.7 99.3 2788000 99.3 0.7 2788000
2/2 Sample Output 4 3895 3 3655 1 510 1 2788000 2 2788000