## page was renamed from 程序设计练习44——zju2539——Energy Minimization
= Energy Minimization =
Time limit: 1 Seconds   

Memory limit: 32768K  

Many of the problems that arise in early computer vision can be naturally expressed in terms of minimization of an energy function. Typically, researchers need to rely on general-purpose optimization techniques such as simulated annealing, which is extremely slow in practice. Some functions that have a restricted form can be solved efficiently using subtle algorithms. In this problem your task is to write a program to find the minimal value of a special class of energy functions widely used in image processing.

Suppose an image has R rows and C columns. We can assign each of the pixel a number ranging from 1 to R * C depending on its scan-line order. We define n = R * C and the energy function is in the form of

{{http://acm.zju.edu.cn/showimg.php?cid=138&pid=1005&file=1.gif}}

where
 * j in N(i) means that the pixel j is in the left, right, top or bottom neighbor of pixel i;
 * the integer pi (0 <= pi <= 255) is the gray level of the pixel i;
 * xi (xi in {0, 1}) is the assigned label to the pixel i; and
 * the integers v0 and v1 (0 <= v0, v1 <= 255) are the prior estimation of the gray level of the pixels labeled 0 and 1 respectively.

== Input ==

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each test case contains four integers R, C (2 <= R, C <= 20), v0 and v1. The following R lines contain C integers each, which are the gray level of the pixels. The proper ranges are shown in the problem description.

== Output ==

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each case, output the minimized energy value in a single line.

== Sample Input ==
{{{
3

2 2 24 91
236 224
250 248

3 3 144 194
44 33 24
92 4 227
47 63 35

2 4 111 19
65 86 109 153
115 186 146 112
}}}

== Sample Output ==
{{{
Case 1:
594

Case 2:
893

Case 3:
230
}}}