g[i][j]表示前i个数字选出j段的最大分值

当 m=2 时

    f[i][j][k]表示第一列前i个数字，第二列前j个数字选出k个子矩阵的最大分值

    f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);

    f[i][j][k]=max{f[i][j][k],f[x][j][k-1]+s1[i]-s1[x]};

    f[i][j][k]=max{f[i][j][k],f[i][y][k-1]+s2[j]-s2[y]};

    当 i=j 时 

        f[i][j][k]=max{f[i][j][k],f[x][x][k-1]+s1[i]-s1[x]+s2[i]-s2[x]};

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=101,M=3,K=11;
int n,m,p,s[N],s1[N],s2[N];
int g[N][K],f[N][N][K];

void work1()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d",s+i);
		s[i]+=s[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=p;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\n",g[n][p]);
}
void work2()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",s1+i,s2+i);
		s1[i]+=s1[i-1];s2[i]+=s2[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=p;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\n",f[n][n][p]);
}
					
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	if(m==1)	work1();
	else work2();
}