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 <set>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

typedef pair<int, int> data;

int memo[1<<15];
int W;
vector<int> vk;
vector<int> w;
vector<int> wm;
vector<vector<int> > wss;

int nap(int flag){
  if(flag == 0) return 0;
  if(memo[flag]) return memo[flag];

  int ret = 10000;

  for(int i = 1; i < (1 << (int)w.size()); i++){
    if(wm[i] <= W && (i | flag) == flag)
      ret = min(ret, 1 + nap(flag ^ i));
  }

  return memo[flag] = ret;
}


int main(){
  int n = getInt();
  int m = getInt() - 1;
  W = getInt();

  vector<int> k(n);
  int cnt = 0;

  REP(i,n){
    k[i] = getInt();
    if(k[i] != 0 || i == 0){
      vk.push_back(i);
      wss.push_back(vector<int>());
      REP(j,k[i]){
        int ww = getInt();
        if(i != 0){
          wss[wss.size() - 1].push_back(cnt++);
          w.push_back(ww);
        }
      }
    }
  }

  int all = w.size();
  if(all == 0){
    puts("0");
    return 0;
  }

  wm = vector<int>(1<<all);

  REP(i,1<<all) REP(j,all) if(i & (1<<j))
    wm[i] += w[j];

  int ks  = wss.size();

  int ans = vk[ks - 1] - m;
  int flag = 0;
  for(int i = ks - 1; i > 0; i--){
    REP(j,wss[i].size())
      flag |= (1 << wss[i][j]);

    int dist = vk[i] - vk[i - 1];
    ans += dist + (dist + dist) * (nap(flag) - 1);
    // printf("%d => %d (%d)\n", vk[i], vk[i - 1], ans);
  }

  printf("%d\n", ans);

  return 0;
}