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 <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI  = acos(-1.0);


int main(){
	int n,m,W;
	cin>>n>>m>>W;
	vvi b(n,vi());
	REP(i,n){
		int k;
		cin>>k;
		REP(j,k){
			int w;
			cin>>w;
			b[i].push_back(w);
		}
	}

	int ans=0;
	for(int i=n-1;i>m-1;i--){
		if(b[i].size()){
			ans=i-m+1;
			break;
		}
	}
	for(int i=n-1;i>0;i--){
		sort(ALL(b[i]));
		while(b[i].size()){
			int remain=W;
			while(1){
				vi::iterator it=upper_bound(ALL(b[i]),remain);
				if(it==b[i].begin()){
					break;
				}
				it--;
				b[i-1].push_back(*it);
				remain-=*it;
				b[i].erase(it);
			}
			ans++;
			if(b[i].size()){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}