解题思路

由于 $w \le 10$，可以对每个传闻的线索数量做状态压缩。一个传闻只关心三种状态：

超过 $2$ 条线索没有额外收益，因此统一截断为 $2$。

题目内容

在《逆水寒》的江湖中，你的游历小人最近去往了“沧澜”海底与“长白山”雪境等新地图，在这里，江湖中流传着许多扑朔迷离的未解传闻。

为了探寻真相，你打算为你的游历小人规划路线。你手头准备的预算共有 $m$ 交子。

大宋版图内一共有 $n$ 个著名的打卡胜地可选。游历第 $i$ 个胜地需要消耗 $a_i$ 交子。根据“千机阁”的情报，在特定的胜地打卡，可以获得关于某些“未解传闻”的线索（会对给定的若干个传闻各提供 $1$ 条线索）。

江湖规矩讲究“孤证不立”。对于任意一个“未解传闻”，只有当收集到至少 $2$ 条来自不同胜地的线索时，该传闻的真相才会被彻底揭开（超过 $2$ 条线索被视为冗余信息，无额外奖励）。

每个胜地最多只能游历一次。你可以自由选择游历若干个胜地，只要总花费不超过 $m$。请计算：经过合理规划，最多有多少个不同的“未解传闻”能被彻底揭开真相。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 24$）代表数据组数，每组测试数据描述如下：

• 第一行输入三个整数 $n, m, w$（$1 \le n \le 2 \times 10^3$；$1 \le m \le 10^9$；$1 \le w \le 10$），分别表示可选的胜地数量、游历总预算、江湖中未解传闻的总数量（传闻编号为 $1,2,\dots,w$）。
• 此后 $n$ 次输入胜地信息。第 $i$ 次：
  • 先输入两个整数 $a_i, k$（$1 \le a_i \le 10^9$；$1 \le k \le w$），分别代表该胜地的游历花费、能提供的线索数量；
  • 换行输入 $k$ 个两两不同的整数，表示该胜地能提供线索的传闻编号，每个编号在 $[1,w]$ 范围内。

除此之外，保证单个测试文件内 $n$ 的总和不超过 $2 \times 10^3$，$w$ 的总和不超过 $20$。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最多可以被彻底揭开（获得至少两条线索）的传闻个数。

样例1

输入

3
4 5 3
2 2
1 2
3 2
1 3
2 1
2
4 2
2 3
3 3 2
2 1
1
2 1
2
3 2
1 2
2 2 3
2 2
1 2
2 1
3

输出

1
0
0