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<cstdlib>
#include<cmath>
#include<vector>
#include<cassert>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
const int N = 18;
int bit[10010];
int dp[1<<N];
int w[1<<N];
int h[1<<N];

int solve(int n,int st,const int wlim){
  if (st == (1<<n)-1){
    return dp[st] = 0;
  }
  int &ret = dp[st];
  if (ret != -1){
    return ret;
  }
  ret = (1<<20);
  REP(i,1,(1<<n)){
    if (i&st)continue;
    int score = h[i];
    if (wlim < w[i])continue;
    ret = min(ret,solve(n,st|i,wlim)+1);
  }
  return ret;
}


int main(){
  int n,m,wlim;
  while(cin>>n>>m>>wlim && n){
    rep(i,n)bit[i] = 0;
    m--;
    int maxheight = 0;
    vector<int> height,weight;
    rep(i,n){
      int cnt;
      cin>>cnt;
      rep(j,cnt){
	int tmp;
	cin>>tmp;
	bit[i] |= (1<<height.size());
	height.push_back(i);
	weight.push_back(tmp);
	maxheight = i;
      }
    }
    if (maxheight == 0){
      cout << 0 << endl;
      continue;
    }

    int size = height.size();
    rep(i,(1<<size)){
      h[i] = 0;
      w[i] = 0;
      rep(j,size){
	if ((1<<j)&i){
	  h[i] = max(h[i],height[j]);
	  w[i] += weight[j]; 
	}
      }
    }
    rep(i,(1<<N))dp[i] = -1;
    solve(size,0,wlim);
    int ans = 0;
    int cur = (1<<size)-1;
    for(int i=n-1;i>0;i--){
      cur ^= bit[i];
      //cout << i <<" " << cur << endl;
      ans += dp[cur]*2;
    }
    int tmp = m > maxheight?m-maxheight:-m;
    //cout << ans <<" " << tmp << " " << ans+tmp << endl;
    cout << ans+tmp << endl;
  }
}