Problem Statement

コンテスト中は下記の問題文で出題されましたが、ジャッジ解では同時に複数個アイテムを所持しなければいけない場合を見逃していました。このケースに対して今回の問題の制約で時間内に解くことはおよそ不可能だと思われます。不適切な出題となって申し訳ありませんでした。

当問題担当者としては、下記問題に対して「同時に所持できるアイテムが1個である」という制約を入れれば適切な出題となったと考えています。(9/15 17:47)

中野さんの住む世界では，自分の作った道具で穴を掘り，洞窟を探検することがブームになっている．

道具は $M$ 種類存在し，鉄鉱石を加工することで作ることができる． いくつかの道具は鉄鉱石だけで作ることができるが，道具によっては鉄鉱石に加え，別の道具を利用しないと作れないものもある． また，一部の道具は，いったん他の道具の作成に使うと壊れてしまい，そのままでは利用できなくなる．

壊れているかいないかに関わらず，道具を分解すると鉄鉱石に戻り，他の道具の材料として再利用できる． ただし，分解によって得られる鉄鉱石の量は，その道具を作るのに必要とした鉄鉱石の量よりも減ってしまう．

中野さんは探検のためにどうしても欲しい道具があり，今持っている $N$ 個の鉄鉱石から作れないかと考えている． 残念なことに，中野さんの住む世界では，特別な道具がないとコンピュータを作ることができない． あなたの仕事は，中野さんの代わりに，欲しい道具が作れるかどうかを判定することである．

Input

入力は以下の形式で与えられる．

$M$ $N$ $K$
$a_1$ $b_1$ $c_1$ $d_1$
$s_{1,1}$ $v_{1,1,1}$ $v_{1,1,2}$ ... $v_{1,1,s_{1,1}}$
$s_{1,2}$ $v_{1,2,1}$ $v_{1,2,2}$ ... $v_{1,2,s_{1,2}}$
:
:
$s_{1,d_{1}}$ $v_{1,d_{1},1}$ $v_{1,d_{1},2}$ ... $v_{1,d_{1},s_{1,d_{1}}}$
$a_2$ $b_2$ $c_2$ $d_2$
:
:
$a_M$ $b_M$ $c_M$ $d_M$
$s_{M,1}$ $v_{M,1,1}$ ... $v_{M,1,s_{M,1}}$
:
:
$s_{M,d_{M}}$ $v_{M,d_{M},1}$ $v_{M,d_{M},2}$ ... $v_{M,d_{M},s_{M,d_{M}}}$

1行目には，3つの数 $M, N, K$ が与えられる． $M$ は作れる道具の種類数，$N$ は中野さんが持っている鉄鉱石の数，$K$ は中野さんが手に入れたい道具の番号である．

続く行には，1番目から $M$ 番目までの道具の情報が順番に与えられる． 各道具の情報は，$a_i$, $b_i$, $c_i$, $d_i$ の4つの数を含む行から始まる． $a_i$ はこの道具を作成するために必要な鉄鉱石の個数， $b_i$ はこの道具を分解した時に得られる鉄鉱石の個数を表す．

$c_i = 0$ のとき，$i$ 番目の道具は1回使うと壊れてしまう． $c_i = 1$ のときは，何回でも使うことができる．

続く $d_i$ 行には，この道具を作るために必要となる道具の組み合わせが，1行に1つ与えられる． これらの行は，必要な道具の個数 $s_{i,j}$ から始まり，$s_{i,j}$ 個の数 $v_{i,j,1}, v_{i,j,2}, \cdots, v_{i,j,s_{i,j}}$ がその後に続く． $v_{i,j,k}$ は，道具 $i$ を作るために必要となる道具の組み合わせである． これらの道具をすべて所持していないと，$i$ 番目の道具を作成することはできない． また， $d_i$ 個の組み合わせのうち，どれか1つでも満たしていれば，道具 $i$ を作ることができる． $d_i = 0$ のとき，道具 $i$ は他の道具を使わずに作ることができる．

Constraints

• $1 \le M \le 18$
• $0 \le N \le 10^6$
• $1 \le K \le M$
• $1 \le b_i < a_i \le 10^6$
• $0 \le d_{i} \le 3$
• $1 \le v_{i,j,k} \le M$
• $v_{i,j,k} \neq v_{i,j,k'} \quad\text{if}\, k \neq k'$

Output

$K$ 番目の道具が作成可能なら yes ，そうでないなら no と出力せよ．

Sample Input 1

4 10 4
4 3 0 0
4 3 0 0
2 1 0 1
1 2
2 1 0 1
2 1 3

Output for the Sample Input 1

yes

Sample Input 2

4 8 4
4 3 1 0
4 3 0 0
2 1 0 1
1 2
2 1 0 1
2 1 3

Output for the Sample Input 2

no

Sample Input 3

4 8 4
4 3 1 0
4 3 0 0
2 1 0 2
1 1
1 2
2 1 0 1
2 1 3

Output for the Sample Input 3

yes

Sample Input 4

5 10 4
5 4 1 0
5 1 1 0
5 1 0 1
1 2
6 1 0 2
1 5
2 3 1
3 2 0 1
1 1

Output for the Sample Input 4

yes

Sample Input 5

2 10 2
5 1 0 1
1 2
5 1 0 1
1 1

Output for the Sample Input 5

no