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 REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
inline void update(pair<int, int>& x, const pair<int, int>& y){
    if(x > y) x = y;
}
int calc(const vector<int>& w, int MAX){
    const int INF = 100000000;
    int n = w.size();
    pair<int, int> dp[1 << 15];
    REP(s, 1 << n) dp[s] = make_pair(INF, INF);
    dp[0] = make_pair(0, 0);
    for(int s = 0; s < (1 << n); s++){
        for(int i = 0; i < n; i++){
            if(!(s >> i & 1)){
                if(dp[s].second + w[i] > MAX){
                    update(dp[s | (1 << i)], make_pair(dp[s].first + 1, w[i]));
                }else{
                    update(dp[s | (1 << i)], make_pair(dp[s].first, dp[s].second + w[i]));
                }
            }
        }
    }
    int times = dp[(1 << n) - 1].first + (dp[(1 << n) - 1].second > 0 ? 1 : 0);
    return 2 * (times - 1) + 1;
}

int main(){
    int N, M, W;
    while(cin >> N >> M >> W){
        vector<int> w[10000];
        REP(i, N){
            int K;
            cin >> K;
            while(K--){
                int t;
                cin >> t;
                w[i].push_back(t);
            }
        }
        vector<int> have;
        int cost = 0;
        int last_calc = 0;
        for(int i = N - 1; i > 0; i--){
            if(w[i].empty()){
                cost += last_calc;
            }else{
                if(have.empty()) cost += abs((i + 1) - M);
                have.insert(have.end(), w[i].begin(), w[i].end());
                cost += (last_calc = calc(have, W));
            }
        }
        cout << cost << endl;
    }
    return 0;
}