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<cstdio>
#include<vector>
#include<cstdlib>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

int main(){
	int n,m,W; scanf("%d%d%d",&n,&m,&W); m--;
	vector<int> floor[10000],a; // eKÉ é×¨, ×¨Ìd³
	rep(i,n){
		int k; scanf("%d",&k);
		floor[i].resize(k);
		rep(j,k){
			int w; scanf("%d",&w);
			floor[i][j]=a.size();
			a.push_back(w);
		}
	}

	static int sum[1<<15];
	rep(S,1<<a.size()) rep(i,a.size()) if(S&(1<<i)) sum[S]+=a[i];

	static int dp[1<<15];
	rep(S,1<<a.size()) dp[S]=(S==0?0:INF);
	rep(S,1<<a.size()) for(int T=S;T;T=T-1&S) {
		if(sum[T]<=W) dp[S]=min(dp[S],dp[S-T]+1);
	}

	int top=0;
	rep(i,n) if(floor[i].size()>0) top=i;

	if(top==0){ puts("0"); return 0; }

	int ans=abs(m-top),S=0;
	for(int i=top;i>0;i--){
		rep(j,floor[i].size()) S|=1<<floor[i][j];
		ans+=2*dp[S]-1;
	}
	printf("%d\n",ans);

	return 0;
}