Problem: Problem

Tomorrow is finally the day of the excursion to Maizu Elementary School. Gatcho, who attends Maizu Elementary School, noticed that he had forgotten to buy tomorrow's sweets because he was so excited. Gaccho wants to stick to sweets so that he can enjoy the excursion to the fullest.


Gaccho gets a $ X $ yen allowance from his mother and goes to buy sweets. However, according to the rules of elementary school, the total amount of sweets to bring for an excursion is limited to $ Y $ yen, and if it exceeds $ Y $ yen, all sweets will be taken up by the teacher.

There are $ N $ towns in the school district where Gaccho lives, and each town has one candy store. Each town is assigned a number from 1 to $ N $, and Gaccho lives in town 1. Each candy store sells several sweets, and the price per one and the satisfaction level that you can get for each purchase are fixed. However, the number of sweets in stock is limited. Also, Gaccho uses public transportation to move between the two towns, so to move directly from town $ i $ to town $ j $, you only have to pay $ d_ {i, j} $ yen. It takes.

At first, Gaccho is in Town 1. Gaccho should make sure that the sum of the total cost of moving and the price of the sweets you bought is within $ X $ yen, and the total price of the sweets you bought is within $ Y $ yen. I'm going to buy sweets. You must have arrived at Town 1 at the end. Gaccho wants to maximize the total satisfaction of the sweets he bought. Find the total satisfaction when you do the best thing.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N \ leq 14 $
* $ 1 \ leq X \ leq 10000 $
* $ 1 \ leq Y \ leq min (1000, X) $
* $ 1 \ leq K \ leq 300 $
* $ 1 \ leq a_i \ leq 1000 $
* $ 1 \ leq b_i \ leq 1000 $
* $ 1 \ leq c_i \ leq 1000 $
* $ 0 \ leq d_ {i, j} \ leq 10000 $
* $ d_ {i, i} = 0 $

Input

All inputs are given as integers in the following format:

$ N $ $ X $ $ Y $
Information on candy stores in town 1
Information on candy stores in town 2
...
Information on candy stores in town $ N $
$ d_ {1,1} $ $ d_ {1,2} $ ... $ d_ {1, N} $
$ d_ {2,1} $ $ d_ {2,2} $ ... $ d_ {2, N} $
...
$ d_ {N, 1} $ $ d_ {N, 2} $ ... $ d_ {N, N} $


On the first line, the number of towns $ N $, the amount of money you have $ X $, and the maximum amount you can use to buy sweets $ Y $ are given, separated by blanks.
From the second line, information on each $ N $ candy store is given.
In the following $ N $ row and $ N $ column, the amount $ d_ {i, j} $ required to go back and forth between town $ i $ and town $ j $ is given, separated by blanks.


Information on candy stores in each town is given in the following format.

$ K $
$ a_1 $ $ b_1 $ $ c_1 $
$ a_2 $ $ b_2 $ $ c_2 $
...
$ a_K $ $ b_K $ $ c_K $


The first line gives $ K $, the number of types of sweets sold at the candy store. In the following $ K $ line, the price of one candy $ a_i $, the satisfaction level $ b_i $ per candy, and the number of stocks $ c_i $ are given, separated by blanks.

Output

Output the maximum value of the total satisfaction level on one line.

Examples

Input

1 10 10
3
1 10 1
2 20 2
3 30 3
0


Output

100


Input

2 10 10
3
1 10 1
2 20 2
3 30 3
1
5 200 1
0 2
3 0


Output

200


Input

3 10 10
1
1 1 1
1
3 3 3
1
5 5 5
0 1 0
1 0 0
0 1 0


Output

10


Input

4 59 40
1
7 6 3
1
10 3 9
2
9 8 5
7 6 10
4
8 2 9
1 7 1
7 7 9
1 2 3
0 28 7 26
14 0 10 24
9 6 0 21
9 24 14 0


Output

34

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 15

struct Data{
	Data(int arg_price,int arg_value,int arg_num){
		price = arg_price;
		value = arg_value;
		num = arg_num;
	}
	int price,value,num;
};

struct Info{

	int num_item;
	vector<Data> V;
};

int N,X,Y;
int POW[SIZE];
int min_dist[SIZE][SIZE];
int TSP[1 << 14][SIZE];
int dp_each[SIZE][305][1005],dp_each2[SIZE][1005];
int dp_A[1 << 7][1005],dp_B[1 << 7][1005];
Info info[SIZE];


int main(){

	POW[0] = 1;
	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
	}

	scanf("%d %d %d",&N,&X,&Y);

	int price,value,num;

	for(int i = 0; i < N; i++){

		scanf("%d",&info[i].num_item);
		for(int k = 0; k < info[i].num_item; k++){

			scanf("%d %d %d",&price,&value,&num);
			info[i].V.push_back(Data(price,value,num));
		}
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){

			scanf("%d",&min_dist[i][k]);
		}
	}

	for(int i = 0; i < N; i++){ //14

		for(int k = 0; k <= info[i].num_item; k++){
			for(int p = 0; p <= Y; p++){
				dp_each[i][k][p] = -BIG_NUM;
			}
		}

		for(int k = 0; k <= Y; k++){

			dp_each2[i][k] = -BIG_NUM;
		}

		dp_each[i][0][0] = 0;
		dp_each2[i][0] = 0;

		for(int k = 0; k < info[i].num_item; k++){ //300

			for(int p = 0; p <= Y; p++){

				dp_each[i][k+1][p] = dp_each[i][k][p];
			}

			int num = info[i].V[k].num;
			int mult;

			for(int p = 1; num > 0; p *= 2){
				mult = min(p,num);
				for(int w = Y; w-mult*info[i].V[k].price >= 0; w--){
					if(dp_each[i][k+1][w-mult*info[i].V[k].price] == -BIG_NUM)continue;
					dp_each[i][k+1][w] = max(dp_each[i][k+1][w],
							dp_each[i][k+1][w-mult*info[i].V[k].price]+mult*info[i].V[k].value);
					dp_each2[i][w] = max(dp_each2[i][w],dp_each[i][k+1][w]);
				}
				num -= mult;
			}
		}

		for(int k = 1; k <= Y; k++){

			dp_each2[i][k] = max(dp_each2[i][k],dp_each2[i][k-1]);
		}
	}

	if(N == 1){

		printf("%d\n",dp_each2[0][Y]);
		return 0;
	}

	//ワーシャルフロイド
	for(int mid = 0; mid < N; mid++){
		for(int start = 0; start < N; start++){
			for(int goal = 0; goal < N; goal++){

				min_dist[start][goal] = min(min_dist[start][goal],min_dist[start][mid]+min_dist[mid][goal]);
			}
		}
	}

	//TSP
	for(int state = 0; state < POW[N]; state++){
		for(int town = 0; town < N; town++){

			TSP[state][town] = BIG_NUM;
		}
	}

	TSP[1][0] = 0;
	for(int state = 1; state < POW[N];state++){
		for(int town = 0; town < N; town++){
			if(TSP[state][town] == BIG_NUM)continue;

			for(int loop = 0; loop < N; loop++){
				if(state & (1 << loop))continue;

				int next_state = state+POW[loop];
				int next_dist = TSP[state][town]+min_dist[town][loop];

				TSP[next_state][loop] = min(TSP[next_state][loop],next_dist);
			}
		}
	}

	vector<int> A,B;
	for(int i = 0; i < N/2; i++){

		A.push_back(i);
	}
	for(int i = N/2; i < N; i++){

		B.push_back(i);
	}

	for(int i = 0; i < POW[A.size()]; i++){
		for(int k = 0; k <= Y; k++){

			dp_A[i][k] = -BIG_NUM;
		}
	}
	dp_A[0][0] = 0;

	for(int state = 0; state < POW[A.size()]; state++){
		for(int i = 0; i <= Y; i++){
			if(dp_A[state][i] == -BIG_NUM)continue;

			for(int loop = 0; loop < A.size(); loop++){
				if(state & (1 << loop))continue;

				for(int k = 0; k <= Y; k++){
					if(i+k > Y)break;

					int next_state = state+POW[loop];
					int next_value = dp_A[state][i]+dp_each2[A[loop]][k];

					dp_A[next_state][i+k] = max(dp_A[next_state][i+k],next_value);
				}
			}
		}

		for(int i = 1; i <= Y; i++){

			dp_A[state][i] = max(dp_A[state][i],dp_A[state][i-1]);
		}
	}

	for(int i = 0; i < POW[B.size()]; i++){
		for(int k = 0; k <= Y; k++){

			dp_B[i][k] = -BIG_NUM;
		}
	}
	dp_B[0][0] = 0;

	for(int state = 0; state < POW[B.size()]; state++){
		for(int i = 0; i <= Y; i++){
			if(dp_B[state][i] == -BIG_NUM)continue;

			for(int loop = 0; loop < B.size(); loop++){
				if(state & (1 << loop))continue;

				for(int k = 0; k <= Y; k++){
					if(i+k > Y)break;

					int next_state = state+POW[loop];
					int next_value = dp_B[state][i]+dp_each2[B[loop]][k];

					dp_B[next_state][i+k] = max(dp_B[next_state][i+k],next_value);
				}
			}
		}

		for(int i = 1; i <= Y; i++){

			dp_B[state][i] = max(dp_B[state][i],dp_B[state][i-1]);
		}
	}

	int ans = 0;

	for(int state_A = 1; state_A < POW[A.size()]; state_A++){

		int num_A = 0;
		for(int loop = 0; loop < A.size(); loop++){
			if(state_A & (1 << loop)){
				num_A += POW[A[loop]];
			}
		}

		for(int state_B = 0; state_B < POW[B.size()]; state_B++){

			int num_B = 0;
			for(int loopB = 0; loopB < B.size(); loopB++){
				if(state_B & (1 << loopB)){
					num_B += POW[B[loopB]];
				}
			}

			int all_state = num_A+num_B;
			int path_cost = BIG_NUM;

			for(int i = 0; i < N; i++){
				if(!(POW[i]&all_state))continue;

				path_cost = min(path_cost,TSP[all_state][i]+min_dist[i][0]);
			}

			int limit = Y;
			if(X-Y < path_cost){

				limit = Y-(path_cost-(X-Y));
			}

			for(int budget_A = 0; budget_A <= limit; budget_A++){
				int budget_B = limit-budget_A;

				ans = max(ans,dp_A[state_A][budget_A]+dp_B[state_B][budget_B]);
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}