1 #include <iostream>
2 #define BIT(X,I) (((X)/p[I])%3)
3 const int p[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}, oo = 1000000000;
4 int f[2][59049], g[59049], h[59049][11], m, n, v[10][10], nth, l = 0;
5 using namespace std;
6
7 void P3() {
8 nth = 1;
9 int s[11];
10 for (int k = 0; k < p[10]; k++) {
11 int i = k, j = 0, t = 1, flag = 0;
12 while (i) {
13 if (i % 3 == 1)s[++t] = j;
14 else if (i % 3 == 2) if (!t)break;
15 else {
16 if (!flag && t == 1)flag = 1, t--;
17 else h[k][s[t]] = j, h[k][j] = s[t--];
18 }
19 i /= 3, j++;
20 }
21 if (!t && !i && flag)g[l++] = k;
22 }
23 }
24
25 void init() {
26 for (int i = 1; i <= m; i++)
27 for (int j = 1; j <= n; j++)
28 if (n <= m) scanf("%d", &v[i][j]);
29 else scanf("%d", &v[j][i]);
30 if (n > m) swap(n, m);
31 }
32
33 void inc(int &a, int b) {
34 if (a < b)a = b;
35 }
36
37 int main() {
38 P3();
39 while (scanf("%d%d", &m, &n) != EOF) {
40 init();
41 for (int k = 0; g[k] < p[n + 1]; k++) f[0][g[k]] = -oo;
42 f[0][2] = 0;
43 for (int i = 1; i <= m; i++)
44 for (int j = 1; j <= n; j++) {
45 if (j == 1) for (int k = l - 1; k >= 0; k--)
46 if (g[k] % 3)f[0][g[k]] = -oo;
47 else f[0][g[k]] = f[0][g[k] / 3];
48 for (int k = 0; g[k] < p[n + 1]; k++) f[1][g[k]] = -oo;
49 for (int kk = 0; g[kk] < p[n + 1]; kk++) {
50 int k = g[kk], s = BIT(g[kk], j - 1), t = BIT(g[kk], j), xx = f[0][k] + v[i][j];
51 if (!s && !t) {
52 inc(f[1][k], f[0][k]);
53 inc(f[1][k + p[j - 1] + 2 * p[j]], xx);
54 } else if (!s) {
55 inc(f[1][k], xx);
56 inc(f[1][k - t * (p[j] - p[j - 1])], xx);
57 } else if (!t) {
58 inc(f[1][k], xx);
59 inc(f[1][k + s * (p[j] - p[j - 1])], xx);
60 } else if (s == 2 && t == 1) {
61 inc(f[1][k - 2 * p[j - 1] - p[j]], xx);
62 } else if (s == 1 && t == 1) {
63 inc(f[1][k - p[j - 1] - p[j] - p[h[k][j]]], xx);
64 } else if (s == 2 && t == 2) {
65 inc(f[1][k - 2 * (p[j - 1] + p[j]) + p[h[k][j - 1]]], xx);
66 }
67 }
68 memcpy(f[0], f[1], sizeof (f[1]));
69 }
70 printf("Case %d: %d\n", nth++, f[0][2 * p[n]]);
71 }
72 }