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 <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
 
const int inf=1<<28;

vector<int> weight;
int floors[10010];

int sum[1<<15];
int dp[1<<15];
 
int main(){
    int n,m,limit;
    cin >> n >> m >> limit;
    
    rep(i,n){
        int k;
        cin >> k;
        floors[i]=0;
        rep(j,k){
            int w;
            cin >> w;
            floors[i]|=(1<<int(weight.size()));
            weight.push_back(w);
        }
    }

    int k=weight.size();
    const int all=(1<<k)-1;
 
    if(floors[0]==all){
        puts("0");
        return 0;
    }
    
    rep(mask,1<<k) dp[mask]=inf;
    rep(mask,1<<k)rep(i,k)if(mask&(1<<i)) sum[mask]+=weight[i];
    
    dp[0]=0;
    rep(mask,1,1<<k){
        for(int smask=mask;smask>0;smask=(smask-1)&mask){
            int tmask=mask^smask;
            if(sum[smask]<=limit) chmin(dp[mask],dp[tmask]+1); 
        }
    }

    int ans=0,cmax=m;
    rep(i,n) if(floors[i]!=0) chmax(cmax,i+1);
    
    ans+=cmax-m;
    rrep(i,cmax,1){
        ans+=2*dp[floors[i]]-1,floors[i-1]|=floors[i];
    }
    cout << ans << endl; 
    return 0;
}