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>
using namespace std;

const int MAXN = 16;
const int INF = 1<<28;

int n, m, W;
vector<vector<int> > w;
int N;
vector<int> weight;
int sum[1<<MAXN], mem[1<<MAXN];

int rec(int b) {
  int &res = mem[b];
  if(res != -1) return res;
  if(b == 0) return res = 0;
  res = INF;
  for(int k = b; k > 0; k = k-1&b) {
    if(sum[k] <= W) res = min(res, rec(b - k) + 1);
  }
  return res;
}

int main() {
  while(cin >> n >> m >> W) {
    int top = 0;
    --m;
    weight.clear();
    w = vector<vector<int> >(n);
    for(int i = 0; i < n; ++i) {
      int k; cin >> k;
      w[i].resize(k);
      if(k) top = i;
      for(int j = 0; j < k; ++j) {
        cin >> w[i][j];
        weight.push_back(w[i][j]);
        w[i][j] = weight.size()-1;
      }
    }
    N = weight.size();

    if(top == 0) {
      cout << 0 << endl;
    } else {
      for(int b = 0; b < (1<<N); ++b) {
        sum[b] = 0;
        for(int j = 0; j < N; ++j) {
          if(b >> j & 1) sum[b] += weight[j];
        }
      }
      memset(mem, -1, sizeof(mem));
      int res = abs(top - m);
      for(int i = top, b = 0; i > 0; --i) {
        for(int j = 0; j < w[i].size(); ++j) {
          b |= 1 << w[i][j];
        }
        res += rec(b) * 2 - 1;
      }
      cout << res << endl;
    }
  }
  return 0;
}