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

using namespace std;

const int INFTY=1<<29;

int main()
{
	for(int n,m,w;cin>>n>>m>>w && n|m|w;){
		vector<vector<int> > a(n);
		vector<int> ws;
		for(int i=0;i<n;i++){
			int k; cin>>k;
			for(int j=0;j<k;j++){
				int w; cin>>w;
				a[i].push_back(ws.size());
				ws.push_back(w);
			}
		}
		
		// SÄÌ×¨ª1KÉ éÈçCGx[^ðmK©ç1KÖÚ·KvÍÈ¢
		if(ws.size()==a[0].size()){
			cout<<0<<endl;
			continue;
		}
		
		vector<int> sum(1<<ws.size());
		for(int i=0;i<ws.size();i++)
			sum[1<<i]=ws[i];
		for(int i=1;i<(1<<ws.size());i++)
			sum[i]=sum[i&-i]+sum[i&i-1];
		
		vector<int> dp(1<<ws.size(),INFTY);
		dp[0]=0;
		for(int i=0;i<ws.size();i++)
			dp[1<<i]=1;
		for(int i=0;i<(1<<ws.size());i++)
			for(int j=i;j;j=i&j-1){
				if(sum[j]<=w)
					dp[i]=min(dp[i],dp[i^j]+1);
			}
		
		int top;
		for(top=n-1;a[top].size()==0;top--)
			;
		
		int res=abs(top-(m-1));
		for(int i=top,bit=0;i>0;i--){
			for(int j=0;j<a[i].size();j++)
				bit|=1<<a[i][j];
			res+=dp[bit]*2-1;
		}
		cout<<res<<endl;
	}
	
	return 0;
}