Wheel of Fortune

The Wheel of Fortune reminds you that the wheel is always turning and life is in a state of constant change. If you’re going through a difficult time right now, rest assured it can only get better from here and soon you will be blessed with good luck and good fortune. Similarly, if things are going amazingly well, know that this too will change and life may return to ’normal’ soon after. This is why it is so important to cherish the blissful moments in your life and make the most of them while they are within reach – because in a flash they could be gone.

Alice wants to make a wheel and decorate it with a circle of jewels. She has $n$ different jewels each of which can be colored in $m$ colors. The arrangement of Jewels always symbolizes fortune. Specifically, when the $i$-th jewel is colored with the $c_i$-th color, it is attached with $a_i$,$c_i$ amount of luck. After coloring all the $n$ jewels, she needs to arrange them in some order $k_1$, $k_2$, · · · , $k_n$(a permutation) such that no two adjacent jewels on the wheel are of the same color. Otherwise she may encounter disasters. Alice enjoys peaceful life and wants to find the minimum possible |max{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$} - min{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$}from all the valid arrangements.

The input starts with a line containing a number $T$ which indicates the number of test cases. Each test case starts with a line containing two numbers $n$ (2 ≤ $n$ ≤ 2000) and $m$ (1 ≤ $m$ ≤ 2000) which indicate the number of jewels and colors respectively. Then n lines follow and each contains m numbers indicating $a_{i,j}$ (1 ≤ $a_{i,j}$ ≤ 1000000)

For each test case, please print only one line in the form of “Case $x$: $ans$”, where $x$ is the test number and $ans$ indicates the answer. If it is impossible for Alice to find a valid arrangement, the answer is -1.

2
4 2
1 2
2 1
1 1
2 2
4 3
8 3 7
2 6 7
2 7 3
5 6 3

Case 1: 1
Case 2: 1

The following picture is the illustration of the samples, in which numbers and shapes indicate indexes of jewels and their colors separately.
In the first sample, we use the first color to color the jewels with indexes 1 and 3, and color the others with the second color.
In the second sample, we use the second color to color the jewel with index 1, the first color to color the jewels with indexes 2 and 3, and the third one to color the jewel with index 4.
The orders of jewels are illustrated below.

642ccpc吉林