问题描述

在比赛中，出了以下问题，但是裁判解决方案中没有考虑同时持有多个物品的情况。根据本次问题的限制条件，在规定的时间内解决此类问题几乎不可能。非常抱歉地给您带来了不合适的提问。

作为问题负责人，我认为在下面的问题中添加“同时只能持有一个物品”的限制将会是一个适当的问题。(9/15 17:47)

在中野先生所居住的世界里，使用自己制作的工具挖掘洞穴成为一种风靡的流行事物。

共有$M$种类型的工具，可以通过加工铁矿石来制作。有些工具只需要铁矿石就可以制作出来，但有些工具除了铁矿石外，还需要使用其他工具。此外，一些工具在用于制作其他工具时会损坏，不能再继续使用。

无论工具是否损坏，都可以将其分解成铁矿石，并将其作为其他工具的材料进行再利用。然而，分解得到的铁矿石数量少于制作该工具所需的铁矿石数量。

中野先生想要一款在探险中必备的工具，他在手头有$N$个铁矿石，想知道能否用这些铁矿石制作出来。遗憾的是，在中野先生所居住的世界中，没有特殊的工具就无法制作计算机。你的工作是代替中野先生判断是否可以制作出他想要的工具。

输入

输入以以下格式给出。

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

第一行给出三个数$M, N, K$。$M$代表可以制作的工具类型数目，$N$代表中野先生拥有的铁矿石数目，$K$代表中野先生想要制作的工具编号。

接下来的行依次给出第一个到第$M$个工具的信息。每个工具的信息以包含四个数$a\_i, b\_i, c\_i, d\_i$的行开始。$a\_i$是制作该工具所需的铁矿石数量，$b\_i$是分解该工具可以得到的铁矿石数量。

当$c\_i = 0$时，工具$i$使用一次后就会损坏；当$c\_i = 1$时，工具$i$可以反复使用。

接下来的$d\_i$行给出了制作该工具所需的工具组合。这些行以所需工具数$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$个组合中只要满足其中任意一个，就可以制作出工具$i$。当$d\_i = 0$时，工具$i$可以单独制作。

约束条件

• $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$
• 当$k \neq k'$时，$v\_{i,j,k} \neq v\_{i,j,k'}$

输出

如果能够制作出第$K$个工具，则输出"yes"；否则输出"no"。

示例输入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

示例输出1

yes

示例输入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

示例输出2

no

示例输入3

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