先进行一遍DP，求出f[i][j]表示第i层取j本书的最大价值和，这个DP利用前缀和可以优化成 O(N³) 。 然后再进行一遍DP，求出g[i][j]表示前i层取j本书的最大价值和，这个DP也是 O(N³) 的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
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;
}
#define size(i) s[i].size()-1
vector<int>s[110],sum[110];
int f[110][10010],g[110][10010],N,M;
int main()
{
	for (int i=1; i<=100; i++) s[i].push_back(0),sum[i].push_back(0);
	N=read(),M=read();
	for (int x,i=1,len,j; i<=N; i++) 
		for (len=read(),j=1; j<=len; j++)
			x=read(),s[i].push_back(x),sum[i].push_back(sum[i][j-1]+s[i][j]);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=size(i); j++)
			for (int k=1; k+size(i)-j-1<=size(i); k++)
				f[i][j]=max(f[i][j],sum[i][size(i)]-(sum[i][k+size(i)-j-1]-sum[i][k-1]));
//	for (int i=1; i<=N; i++,puts(""))
//		for (int j=1; j<=size(i); j++)
//			printf("%d  ",f[i][j]);
	for (int i=1,j,len=0; i<=N; i++)
		for (len+=size(i),j=1; j<=len; j++)
			for (int k=0; k<=size(i); k++)
				if (j>=k && len-(size(i))>=j-k)
					g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][k]);
//	for (int i=1; i<=N; i++,puts(""))
//		for (int j=1; j<=size(i); j++)
//			printf("%d  ",g[i][j]);
	printf("%d\n",g[N][M]);
	return 0;
}