Rafiq lives in a strange square shaped country FONO where each city is equal in size and square in shape and connected to at most four cities. From the top view of the country, it looks like a grid. For simplicity, we assume that each city is recognized by two numbers: the row and column number, starting from (0, 0). Each city is connected by road from those cities which share the same borderline. So from city (i,j), any one can go to city (i−1,j) or city (i+1,j) or city (i,j −1) or city (i,j +1) and no one can move more than one city in a day. The rules of the country are very simple: when any one stays in a city, he must pay an amount of money to that city which covers the cost of staying in that city for one day and the cost to reach any one of the neighbor cities where he wants to go. He can stay in a city as many days as he wants but he needs to pay for each day. Fig: Country FONO Every year the government of FONO organizes a lottery and gives a chance to one person and his F friends to stay in any city of the country without any cost. This lottery is valid for only T days. This year Rafiq has won this lottery and has decided to invite 3 of his friends. He has also decided to bear the cost to reach that city for all of his friends. So he needs to calculate which city is suitable for him to invite that is minimum amount of money required to reach in that city by his friends. Suppose F1 lives at City (0, 0). To reach the city (0, 3), he needs to pay 19. Because after reaching city (0, 3), he need not to pay any money. (Remember that, the lottery is valid for only T days. So all of his friends must reach in the selected city within T days.) Input The input consists of a number of cases (Less than 31). Each case starts with a line specifying three integer numbers N, F, T. Here N (0 < N ≤ 25) represents the size of the country, F (0 < F ≤ 5) represents the number of friends Rafiq wants to invite, and T (0 < T ≤ 25) represents the number of days within which the lottery is valid. After that, N × N positive numbers (< 10000) are given which represents the cost of each city of the country. After that, there are F lines. Each line contains 2 numbers – x and y – representing the current position of Rafiqs friends. Input is terminated by a line where N = F = T = 0.
2/2 Output For each test case, first print the ‘Case #i:’ where i is the test case number, and then print ‘Impossible.’. if it is not possible to find a city where each one can meet within the specified day. If it is possible, print the position of the city and the cost to reach that city. If more than one solution of minimum cost is possible, select the one with minimum row number. If still more than one solution found, print the one with minimum column number. Sample Input 433 4 5 10 20 40 30 40 10 18 53 4 32 52 37 42 43 00 03 23 432 4 5 10 20 40 30 40 10 18 53 4 32 52 37 42 43 00 03 23 000 Sample Output Case #1: Selected city (0,3) with minimum cost 61. Case #2: Impossible.