Problem: Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

3 3 2
1 1
2 1 1
3 1 1 1


Output

8

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
using namespace std;
int p[20];
int q[20];
int cost[1<<15];
int dp[1<<15];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	b--;
	int sz=0;
	int h=0;
	for(int i=0;i<a;i++){
		int d,e;
		scanf("%d",&d);
		for(int j=0;j<d;j++){
			h=i;
			scanf("%d",&e);
			p[sz]=i;
			q[sz]=e;
			sz++;
		}
	}
	bool jimei=true;
	for(int i=0;i<sz;i++)if(p[i])jimei=false;
	if(jimei){
		printf("0\n");return 0;
	}
	for(int i=0;i<(1<<sz);i++)dp[i]=999999999;
	dp[0]=0;
	for(int i=0;i<(1<<sz);i++){
		int w=0;
		for(int j=0;j<sz;j++)if(i&(1<<j))w+=q[j];
		if(w<=c)cost[i]=1;
		else cost[i]=999999999;
	}
	for(int i=0;i<(1<<sz);i++){
		for(int j=(1<<sz)-1-i;j;j=((j-1)&((1<<sz)-1-i))){
			dp[i+j]=min(dp[i+j],dp[i]+cost[j]);
		}
	}
	int ret=0;
	int now=0;
	for(int i=a-1;i;i--){
		for(int j=0;j<sz;j++){
			if(p[j]==i)now+=(1<<j);
		}
		ret+=dp[now]*2;
	}
	if(h>=b)ret-=b;
	else ret+=b-h-h;
	printf("%d\n",ret);
}