Animals are living their painful lives in the zoo. Their activities are limited in a small area without any fun of snacks, alcohol, love or games. They are so upset that they decide to escape in a night. As shown in Figure 1, the paths in the zoo can be expressed by a grid with n × m nodes. All the paths in the grid are two-way, horizontal or vertical or diagonal. Animals start from the upper left corner, and they are free if they can reach the lower right through paths. Figure 1: This is a 3 × 4 nodes grid, the number beside the path indicating how many staff shall be sent to block this path To protect public safety, the police are sent to block some paths to catch all the escaping animals. As it needs certain police staff to block a path, you are required to write a program for the police officer, and tell him how many staff at least shall be sent in order to defeat this Animal Escape. Input Input contains several cases, each describes one escape action. Each case begins with two integers n and m, 3 ≤ n, m ≤ 1000. For the following n lines, there are m − 1 integers in each line, indicating how many staff shall be sent to block the horizontal paths respectively. For the following n − 1 lines, there are m integers in each line, indicating how many staff shall be sent to block the vertical paths respectively. For the following n − 1 lines, there are m − 1 integers in each line, indicating how many staff shall be sent to block the diagonal paths respectively. Each line describes the paths from left to right. All integers in input file are no more than 1, 000, 000. The last case is followed by a line containing two zeros. The size of the input data is about 16MB. Output For each case, output how many staff at least shall be sent to block all animals. Please output in the following format.
2/2 Sample Input 34 564 431 753 5678 8765 555 666 00 Sample Output Case 1: Minimum = 14