1 #include 
 2 #include 
 3 using namespace std;
 4 const int N = 11,INF = 0x7f7f7f7f;
 5 int m,n,mp[1<<21],A[N][N],B[N][N],aim;
 6 
 7 bool who(int sta) { //判断该谁走的函数
 8     int p=m,ans=0;
 9     while(sta) {
10         if(sta&1) {
11             ans+=p;
12         }
13         else {
14             p--;
15         }
16         sta=sta>>1;
17     }
18     return !(ans&1);
19 }
20 
21 void out(int sta) { //输出这个状态(二进制) 
22     int t[300],T=0;
23     fill(t,t+30,0);
24     while(sta) {
25         t[++T] = bool(sta&1);
26         sta=sta>>1;
27     }
28     printf(" ");
29     for(int i=m+n;i>=1;i--) {
30         printf("%d",t[i]);
31     }
32     printf(" ");
33     return;
34 }
35 
36 int DFS(int now) {
37 
38     ///printf("DFS\n");
39 
40     if(mp[now]) { // 记忆化
41         return mp[now];
42     }
43     if(now==aim) {
44         return 0;
45     }
46 
47     bool f = who(now);
48     int p=0,ans=(f?(-INF):INF);
49     for(int i=0;i) {
50         if(now&(1<<i)) {
51             p++;
52         }                          // gay
53         if((!(now&(1<1<<(i+1))))  { /* 10 */ /** 10 */  /// [p+1][m+p-i]
54             int nextsta = (now|(1<1<<(i+1)));
55             int x=p+1;
56             int y=m+p-i;
57             if(f) {
58                 ans=max(ans,DFS(nextsta)+A[x][y]);
59             }
60             else {
61                 ans=min(ans,DFS(nextsta)-B[x][y]);
62             }
63         }
64     }
65     mp[now]=ans;
66     //printf("DFS:");
67     //out(now);
68     //printf("\n");
69     return ans;
70 }
71 
72 int main(){
73     scanf("%d%d",&n,&m);
74     for(int i=1;i<=n;i++) {
75         for(int j=1;j<=m;j++) {
76             scanf("%d",&A[i][j]);
77         }
78     }
79     for(int i=1;i<=n;i++) {
80         for(int j=1;j<=m;j++) {
81             scanf("%d",&B[i][j]);
82         }
83     }
84     int s=0; // 起点
85     for(int i=1;i<=n;i++) {
86         aim=aim<<1|1; // 终点
87         s=s<<1|1;
88     }
89     for(int i=1;i<=m;i++) {
90         s=s<<1;
91     }
92 
93     printf("%d",DFS(s));
94 
95     return 0;
96 }