In this problem you are given a square maze of dimension N with N ∗N blocks. Each block is numbered as follows: N−1,0 N−1,1 ··· ··· ··· ··· 2,0 2,1 2,2 1,0 1,1 1,2 0,0 0,1 0,2 ··· N −1,N −1 ··· ··· ··· ··· ··· ··· ··· 0,N − 1 The maze has only one entry which is at (0, 0) and only one exit which is at (N −1,N −1). From each block you can move in four directions (N, E, W, S) and the cost is 1 for each movement among the maze but collecting treasure does not require any cost. Some blocks contain treasures that you will have to collect. Suppose there are T treasures in the maze and you have to collect at least S (S ≤ T) treasures from them. In this problem, you are requested to find an optimal way from starting location to ending location and take at least S treasures from the maze. Remember that, you can visit a block more than once if you want. Input The first line of the input contains three integers N (N ≤ 30), T (T ≤ 30) and S (S ≤ 10 and S ≤ T) describing the dimension of the maze, number of treasures in the maze and number of treasures that you can take. After that, there are T lines. Each line contains two numbers representing the position of the treasure in the maze. The input may contain multiple test cases and ends with three zeros for N, T and S. Output Each test case produces one line of output. This line should contain the output serial no as shown in the sample output and a number representing the minimum cost which is required to collect the treasures. Sample Input 444 20 21 22
2/2 02 442 20 21 22 02 000 Sample Output Case 1: 10 Case 2: 6