Recycle

Time Limit : 2 sec, Memory Limit : 131072 KB

Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.

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

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

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

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

Input

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

M N K
a1 b1 c1 d1
s1,1 v1,1,1 v1,1,2 ... v1,1,s1,1
s1,2 v1,2,1 v1,2,2 ... v1,2,s1,2
:
s1,d1 v1,d1,1 v1,d1,2 ... v1,d1,s1,d1
:
a2 b2 c2 d2
:
aM bM cM dM
sM,1 vM,1,1 ... vM,1,sM,1
:
sM,dM vM,dM,1 vM,dM,2 ... vM,dM,sM,dM

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

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

ci = 0 のとき,i 番目の道具は 1 回使うと壊れてしまう. ci = 1 のときは,何回でも使うことができる.

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

Constraints

  • 1 ≤ M ≤ 18
  • 0 ≤ N ≤ 106
  • 1 ≤ KM
  • 1 ≤ bi < ai ≤ 106
  • 0 ≤ di ≤ 3
  • 1 ≤ vi,j,kM
  • vi,j,k ≠ vi,j,k' if k ≠ 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 4, Tokyo, Japan, 2014-09-15
http://acm-icpc.aitea.net/
http://jag2014summer-day4.contest.atcoder.jp/