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 static int INF = 1 << 30;

int main()
{
  int n, m, W;
  int weight[15], ptr = 0;
  int bit[10000] = {};
  int sum[1 << 15] = {}, dp[1 << 15];
  int highest = 0;
  fill_n(dp, 1 << 15, INF);

  cin >> n >> m >> W;
  for(int i = 0; i < n; i++) {
    int k;
    cin >> k;
    if(k > 0) highest = i;
    for(int j = 0; j < k; j++) {
      int w;
      cin >> w;
      if(i > 0) {
        weight[ptr] = w;
        bit[i] |= 1 << ptr;
        ++ptr;
      }
    }
  }
  if(ptr == 0) {
    puts("0");
  } else {
    for(int i = 1; i < 1 << ptr; i++) {
      for(int j = 0; j < ptr; j++) {
        if((i >> j) & 1) sum[i] += weight[j];
      }
    } 

    dp[0] = 0;
    for(int i = 1; i < 1 << ptr; i++) {
      for(int j = i; j > 0; j = j - 1 & i) {
        if(sum[j] <= W) dp[i] = min(dp[i], dp[i - j] + 1);
      }
    }
    int ret = 0;
    for(int i = highest, bits = 0; i > 0; i--) {
      ret += dp[bits |= bit[i]] * 2 - 1;
    }
    cout << ret + fabs(highest - m + 1) << endl;
  }
}