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<iostream>
#include<sstream>
#include<vector>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

int n,m,w;
int wi[15], nw;
int bit[10000],sum[1<<15];
int dp[1<<15];
int main(){
	cin>>n>>m>>w;
	rep(i,n){
		int k; cin>>k;
		rep(j,k){
			cin>>wi[nw];
			bit[i]|=1<<nw++;
		}
	}
	rep(i,1<<nw)rep(j,nw)if(i&1<<j)sum[i]+=wi[j];
	rep(i,1<<nw)dp[i]=inf;
	dp[0]=0;
	rep(i,1<<nw)for(int j=i;j;j=j-1&i){
		if(sum[j]<=w)dp[i]=min(dp[i],dp[i-j]+1);
	}
	int top=0;
	rep(i,n)if(bit[i])top=i;
	if(top==0){
		cout<<0<<endl; return 0;
	}
	int ans=abs(m-1-top), h=0;
	for(int i=top;i>0;i--){
		h+=bit[i];
		ans+=dp[h]*2-1;
	}
	cout<<ans<<endl;
	
	return 0;
	
}