单路径最大和问题，设f[i][j][S]表示到达(i,j)，轮廓线状态为S的最优解。
S用4进制m+1位数表示，0表示无插头，1表示左括号，2表示右括号，3表示独立插头。
在DP之前先进行一次预处理，剔除无效状态，并预处理出与每个括号匹配的另一个括号的位置，有效状态只有8000个左右。
然后分类讨论进行转移即可。
#include<cstdio>
const int N=9,M=8320,inf=-1000000000;
int n,m,S,i,j,k,h,z,ans=inf,q[M],id[1<<(N*2)],pre[M],now[M];
char can,c3,st[N+1],p[M][N],tmp[N];
inline int bit(int x,int i){return x>>(i<<1)&3;}
inline void up(int&a,int b){if(a<b)a=b;}
inline void clr(){for(int k=1;k<=q[0];k++)now[k]=inf;}
inline void nxt(){for(int k=1;k<=q[0];k++)pre[k]=now[k];}
int main(){
scanf("%d%d",&n,&m);
S=1<<(2*(m+1));
for(i=0;i<S;i++){
can=1,st[0]=c3=0;
for(j=0;j<=m;j++){
k=bit(i,j);
if(k==1)st[++st[0]]=j;
if(k==2){
if(!st[0]){can=0;break;}
tmp[st[st[0]]]=j;tmp[j]=st[st[0]];
st[0]--;
}
if(k==3)if((++c3)>2){can=0;break;}
}
if(can&&!st[0]){
q[id[i]=++q[0]]=i;
for(j=0;j<=m;j++)p[q[0]][j]=tmp[j];
}
}
clr();
now[1]=0;
nxt();
for(i=1;i<=n;i++){
clr();
for(k=1;k<=q[0];k++)if(pre[k]>inf&&!bit(q[k],m))now[id[q[k]<<2]]=pre[k];
nxt();
for(j=1;j<=m;j++){
scanf("%d",&z),up(ans,z),clr();
for(h=1;h<=q[0];h++)if(pre[h]>inf){
int v=pre[h]+z,k=q[h],x=bit(k,j-1),y=bit(k,j),e=k^(x<<((j-1)<<1))^(y<<(j<<1));
if(!x&&!y){
up(now[h],v-z);
up(now[id[e^(1<<((j-1)<<1))^(2<<(j<<1))]],v);
up(now[id[e^(3<<((j-1)<<1))]],v);
up(now[id[e^(3<<(j<<1))]],v);
}else if(!x||!y){
int t=x+y;
up(now[id[e^(t<<((j-1)<<1))]],v);
up(now[id[e^(t<<(j<<1))]],v);
if(t==3){if(!e)up(ans,v);}
else{
if(x)up(now[id[e^(x<<(p[h][j-1]<<1))]],v);
else up(now[id[e^(y<<(p[h][j]<<1))]],v);
}
}else if(x==1&&y==1)up(now[id[e^(3<<(p[h][j]<<1))]],v);
else if(x==2&&y==1)up(now[id[e]],v);
else if(x==2&&y==2)up(now[id[e^(3<<(p[h][j-1]<<1))]],v);
else if(x==3&&y==3){if(!e)up(ans,v);}
else if(x==3)up(now[id[e^(y<<(p[h][j]<<1))]],v);
else if(y==3)up(now[id[e^(x<<(p[h][j-1]<<1))]],v);
}
nxt();
}
}
return printf("%d",ans),0;
}