问题陈述
在比赛过程中,提出了以下问题,但评委的解决方案忽略了必须同时持有多个项目的情况。考虑到这个问题的限制,在时间内解决这个问题几乎是不可能的。我很抱歉问了一个不恰当的问题。
作为这个问题的负责人,我相信如果我们加上“同时只能持有一件物品”的约束,下面的问题就会被恰当地提出。(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$是中野先生想要获得的工具数量。
在下面的行中,按顺序给出了从第 1 号到第 $M$ 号工具的信息。 每个工具的信息以包含四个数字的行开头:$a_i$、$b_i$、$c_i$、$d_i$。 $a_i$表示制作该工具所需的铁矿石数量,$b_i$表示拆卸该工具时获得的铁矿石数量。
当$c_i = 0$时,第$i$个工具将在使用一次后损坏。当$c_i = 1$时,可以使用任意次。
在下面的 $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$
- $v_{i,j,k} \neq v_{i,j,k'} \quad\text{if}\, k \neq 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 1 2 2 1 0 1 2 1 3
样本输入 3 的输出
yes
示例输入 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
样本输入 4 的输出
yes
示例输入 5
2 10 2 5 1 0 1 1 2 5 1 0 1 1 1
样本输入 5 的输出
no