学步园

#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,K,s[101],s1[101],s2[101],g[101][11],f[101][101][11];
inline void solve1(){
	for(int i=1;i<=n;i++)
 		s[i]=s[i-1]+read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=K;j++){
			g[i][j]=g[i-1][j];
			for(int k=i-1;k>=0;k--)
				g[i][j]=max(g[i][j],g[k][j-1]+s[i]-s[k]);
		}
	printf("%d",g[n][K]);
}
inline void solve2(){
	for(int i=1;i<=n;i++)
		s1[i]=s1[i-1]+read(),
		s2[i]=s2[i-1]+read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=K;k++){
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int x=i-1;x>=0;x--)
					f[i][j][k]=max(f[i][j][k],f[x][j][k-1]+s1[i]-s1[x]);
				for(int y=j-1;y>=0;y--)  
               		f[i][j][k]=max(f[i][j][k],f[i][y][k-1]+s2[j]-s2[y]);  
            	if(i==j)for(int x=i-1;x>=0;x--)  
               		f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+s1[i]-s1[x]+s2[j]-s2[x]);  
			}
	printf("%d",f[n][n][K]);
}
int main(){
	n=read();m=read();K=read();
	if(m==1)solve1();
	else solve2();
	return 0;
}