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 <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

const double EPS=(1e-10);
typedef long long ll;
typedef pair<int,int> pii;
bool EQ(double a,double b){
  return abs((a)-(b))<EPS;
}
void fast_stream(){
	std::ios_base::sync_with_stdio(0);
}

int n,m,W;
vector<pii> objs[10001];
vector<int> allObj;
int dp[1<<15];
const int INF=1000000000;
void solve(){
    cin>>n>>m>>W;
    for(int i=0;i<n;i++){
        int K;
        cin>>K;
        for(int j=0;j<K;j++){
            int w;
            cin>>w;
            objs[i].push_back(make_pair(w,allObj.size()));
            allObj.push_back(w);
        }
    }
    dp[0]=0;
    for(int mask=1;mask<(1<<(allObj.size()));mask++){
        int bit=0;
        int allSum=0;
        int res=INF;
        for(int j=0;j<allObj.size();j++){
            bit+=(mask>>j)&1;
            if((mask>>j)&1)allSum+=allObj[j];
        }
        if(bit==1||allSum<=W)res=1;
        else{
            for(int j=((mask-1)&mask);j;j=((j-1)&mask)){
                int k=(mask-j);
                res=min(res,1+dp[j]+dp[k]);
            }
        }
        dp[mask]=res;
    }
    // ツ湘」ツづ個階ツつゥツづァツ渉氾板づ可つィツづォツつキ
    int curMask=0;
    int prvRank=-1;
    int sumCost=0;
    for(int i=n-1;i>=0;i--){
        if(objs[i].size()>=1||i==0){
            if(curMask!=0){
                int diff=prvRank-i;
                sumCost+=dp[curMask]*diff;
            }
            if(prvRank==-1)sumCost+=abs(i-(m-1));
            prvRank=i;
            // bitツ療アツづーツ更ツ新
            for(int j=0;j<objs[i].size();j++)curMask|=(1<<objs[i][j].second);
        }
    }
    if(objs[0].size()==allObj.size())cout<<0<<endl;
    else cout<<sumCost<<endl;
}

int main(){

    solve();

    return 0;
}