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<cmath>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

struct P
{
  int weight,index;
  P(int weight=inf,int index=inf):weight(weight),index(index){}
  bool operator < (const P& a)const
  {
    return weight < a.weight;
  }
};

int n,m,W;

int main()
{
  int k;
  scanf("%d %d %d",&n,&m,&W);
  
  int idx = 0;
  vector<vector<P> > vec;
  vector<int> FLOOR;

  rep(i,n)
    {
      scanf("%d",&k);
      if(k == 0)
	{
	  if(i == 0)
	    {
	      FLOOR.push_back(i);
	      vec.push_back(vector<P>());
	    }
	  continue;
	}
      int cur = vec.size();
      vec.push_back(vector<P>(k));
      FLOOR.push_back(i);
      rep(j,k)
	{
	  scanf("%d",&vec[cur][j].weight);
	}
    }

  if(FLOOR[FLOOR.size()-1] == 0)
    {
      puts("0");
      return 0;
    }

  int ans = FLOOR[FLOOR.size()-1]+1-m;
  for(int i=FLOOR.size()-1;i>=1;i--)
    {
      //cout << "cost = " << FLOOR[i] << " - " << FLOOR[i-1] << endl;
      int cost = FLOOR[i] - FLOOR[i-1];
      assert(cost >= 0);
      int SIZE = vec[i].size();
      //cout << "SIZE = " << SIZE << endl;
      int dp[(1<<SIZE)];
      rep(j,(1<<SIZE))dp[j] = inf;
      dp[0] = 0;
      rep(state,(1<<SIZE))//テ、ツサツ甘」ツ?ョテ」ツδ陛」ツδュテ」ツつ「テ」ツ?ョテァツ環カテヲツウツ?0 -> テ」ツ?セテ」ツ??ァツァツサテ・ツ仰陛」ツ?療」ツ?ヲテ」ツ?ェテ」ツ?? 1 -> テァツァツサテ・ツ仰陛」ツ?療」ツ?淌」ツ?淌」ツ?敕ッツスツ?
	{
	  if(dp[state] == inf)continue;
	  vector<P> tmp;//テ」ツ?セテ」ツ??」ツ?禿」ツ?ョテ」ツδ陛」ツδュテ」ツつ「テ」ツ?ォテ」ツつ凝」ツつづ」ツ?ョテ」ツ?淌」ツ?敕ッツスツ?
	  rep(j,SIZE)
	    {
	      if((state>>j) & 1)continue;
	      tmp.push_back(P(vec[i][j].weight,j));
	    }

	  sort(tmp.begin(),tmp.end());
	  int limit = tmp.size();
	  rep(j,(1<<limit))//テヲツャツ。テ」ツ?ォテァツァツサテ・ツ仰陛」ツ?凖」ツつ凝」ツつづ」ツ?ョ
	    {
	      int sum = 0;
	      int tstate = 0;
	      rep(k,limit)
		{
		  if((j>>k) & 1)
		    {
		      tstate |= (1<<tmp[k].index);
		      sum += tmp[k].weight;
		    }
		}
	      assert(sum >= 0);
	      if(sum > W)continue;
	      assert((state ^ tstate) == (state | tstate));
	      int nstate = state | tstate;
	      dp[nstate] = min(dp[nstate],
			       dp[state]+2);
	    }
	}
      rep(j,vec[i].size())vec[i-1].push_back(vec[i][j]);
      assert((dp[(1<<SIZE)-1]-1)*cost >= 0);
      ans += (dp[(1<<SIZE)-1]-1)*cost;//テヲツ鳴ーテ」ツ?淌」ツ?ェテ・ツ?、テ」ツつ津・ツセツ療」ツつ凝」ツ?淌」ツ?敕ッツスツ?
      assert(ans >= 0);
      //cout << "ans = " << ans << " dp = " << dp[(1<<SIZE)-1] << endl;
    }

  printf("%d\n",ans);//テ」ツ?暗」ツつ凝」ツ?淌」ツ?敕ッツスツ?

  return 0;
}