PEG Judge - WC02 - The Final Battle

Woburn Challenge 2002

Problem 10: The Final Battle

The monkeys and cows have marched to the place designated to host the final battle. It's surprising how much people cooperated even when it came to scheduling wars during the old days! As the cows line up, the monkeys assume their positions as well. This time, the monkeys have protected themselves with metal underwear; you'll no doubt remember the many hours spent rehabilitating the front of their backsides! Bo and the Head-Monkey come face to face in the middle of the field, and engage in a made for TV stare-down. Then, just as the two leaders are about to signal their factions to advance, the skies open, and down descends an alien spaceship.

"We are the intergalactic arbitrators. We cannot allow this battle to continue, for many lives would needlessly be lost. Instead, we propose a game, the winner of which shall gain custody of SCARBERIA!"

The leaders are stunned by this twist, but nonetheless, they agree to the terms proposed by the alien arbitrators. Then, the aliens explain the game.

N members, 1 ≤ N ≤ 100, of each group will be teleported to a distant planet, and placed in identical mazes. This maze has M, 1 ≤ M ≤ 100, doors, and each of these must be opened in order to "solve" the maze. The first group that solves their maze shall be declared the winner. Please remember that the doors must be opened in order and that the same monkey cannot open two consecutive doors!"

Since you are currently in Scarberia, it would be in your best interest to help the Monkeys win this game, so that they may retain control of Scarberia. Otherwise…

Input

The first line contains a single integer, T (1 ≤ T ≤ 50), indicating the number of test cases.
The first line of each test case contains two integers N and M.
The next N lines contain M integers each. The numbers on each line indicate the time it takes for the particular monkey to open each door. So, as an example, the 3rd number on the 2nd line indicates the time Monkey #2 would take to open door #3.