Problem G: Picnic

Problem

明日はいよいよマイヅ小学校の遠足の日である。マイヅ小学校に通うがっちょ君は、楽しみのあまり明日のお菓子を買い忘れていたことに気づいた。 がっちょ君は遠足を最大限楽しむため、お菓子にもこだわりたい。

がっちょ君はお母さんから$X$円のお小遣いをもらってお菓子を買いに行く。ただし、小学校のルールで遠足に持っていくお菓子の合計金額は$Y$円までと決まっており、$Y$円を上回るとお菓子は全て先生に取り上げられてしまう。

がっちょ君の住む学区には$N$個の町があり、各町には1軒の駄菓子屋がある。各町には1から$N$の番号が割り振られており、がっちょ君は町1に住んでいる。 各駄菓子屋ではいくつかのお菓子が売っており、1つあたりの値段、1つ買うごとにがっちょ君が得られる満足度が決まっている。ただし、各お菓子の在庫数には限りがある。 また、がっちょ君は2つの町の間を移動するとき公共交通機関を利用するため、町$i$から町$j$へ直接移動するには$d_{i,j}$円だけお金がかかる。

最初、がっちょ君は町1にいる。がっちょ君は移動にかかる費用の合計と買ったお菓子の値段の合計の和が$X$円以内で、かつ、買ったお菓子の値段の合計が$Y$円以内になるようにお菓子を買いに行く。最後には町1に到着している必要がある。がっちょ君は買ったお菓子の満足度の合計ができるだけ大きくなるようにしたい。がっちょ君が最適な行動をしたときの満足度の合計を求めよ。

Input

入力は以下の形式ですべて整数で与えられる。

$N$ $X$ $Y$
町1の駄菓子屋の情報
町2の駄菓子屋の情報
...
町$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}$

1行目に町の数$N$と所持金$X$、お菓子を買うために使うことができる上限金額$Y$が空白区切りで与えられる。
2行目からは$N$個の各駄菓子屋の情報が与えられる。
続く$N$行$N$列に町$i$と町$j$を直接行き来するために必要な金額$d_{i,j}$が空白区切りで与えられる。

各町の駄菓子屋の情報は以下の形式で与えられる。

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

1行目にその駄菓子屋で売っているお菓子の種類の数$K$が与えられる。続く$K$行にお菓子の1つの値段$a_i$、1つあたりの満足度$b_i$、在庫数$c_i$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $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$

Output

満足度の合計の最大値を1行に出力する。

Sample Input 1

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

Sample Output 1

100

Sample Input 2

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

Sample Output 2

200

Sample Input 3

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

Sample Output 3

10

Sample Input 4

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

Sample Output 4

34