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 <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int dp[1<<15];

int main() {
  int N,M,W;
  cin >> N >> M >> W;
  vector<pii> v;
  int ma = 0;
  
  REP(i, N) {
    int k;
    cin >> k;
    REP(j, k) {
      int a;
      cin >> a;
      if (i) {
        v.push_back(pii(i, a));
        ma = max(ma, i);
      }
    }
  }
  int n = v.size();
  if (n == 0) {
    cout << 0 << endl;
    return 0;
  }
  REP(i, 1<<n) dp[i] = INF;
  dp[0] = 0;
  REP(S, 1<<n) {
    vector<int> tmp;
    REP(i, n) if (S>>i&1) tmp.push_back(i);
    int num = tmp.size();
    REP(tT, 1<<num) {
      int T = 0;
      REP(j, num) if (tT>>j&1) T |= 1<<tmp[j];
      int weight = 0;
      REP(j, n) {
        if (T>>j&1) weight += v[j].second;
      }
      if (weight <= W) {
        dp[S] = min(dp[S], dp[S^T]+1);
      }
    }
  }
  int now = 0;
  int ans = 0;
  for (int i=N-1; i>=1; --i) {
    REP(j,n) if (v[j].first == i) now |= 1<<j;
    ans += dp[now]*2;
  }
  M--;
  ans -= ma;
  ans += abs(M-ma);
  cout << ans << endl;
}