关于 agKc 实在不喜欢自动化于是啥都自己合成这件事

Problem Description

在游戏 minecraft 中，合成是一件非常重要的事，其基本内容是：由若干种不同的物品，合成新的物品。玩家可以通过实现流水线自动化来大幅缩减自己的工作量，但agKc实在不喜欢这样玩，于是选择全靠自己合成。 现一共有 $n$ 种物品，依次编号为 $1 \sim n$。为了更好的描述问题，我们将物品分为两类：

• 原材料：可以直接获取的物品，$\textbf{获取 $1$ 个第 $i$ 种原材料需要花费 $t_i$ 时间} $。
• 合成产物：通过合成获得的物品，可以根据其合成配方，通过消耗若干个其它物品合成。$\textbf{合成不需要花费时间}$。 具体而言，若第 $b$ 种物品为一合成产物，则其合成配方可表示为 $x_1a_1 + x_2a_2 + \dots +x_ka_k \rightarrow b$，即，可以消耗 $x_1$ 个第 $a_1$ 种物品，$x_2$ 个第 $a_2$ 种物品，$\dots$，以及 $x_k$ 个第 $a_k$ 种物品，来合成出一个第 $b$ 种物品。 $\textbf{保证一种物品只会作为一个配方的原料，以及一种配方的产物。}$ 现在 agKc 打算爆肝合成一件物品，并告诉了你所有需要的配方，同时 agKc 的爆肝行为感动了服务器的管理员，管理员决定送给他除了最终产物外的无限的任意 $1$ 种物品，请你计算出，agKc 需求哪一种物品，能使合成出最终产物的耗时最短，并回答出最短耗时。 最终耗时为生产所需原材料的耗时之总和，合成过程不需要花费时间。保证一定可以在有限的时间内生产出最终产物。但由于 agKc 的时间有限，若最短耗时超过了 $10^9$ ，请输出 Impossible。

Input

第一行一个整数 $t$ ($1\leq t \leq 20$)表示测试点数量。每个测试点输入格式如下 第一行两个整数 $n$ ($1\leq n \leq 10^5$) 代表物品的总数量，$k$ ($1\leq k \leq n$) 代表agKc需要合成的物品 接下来 $n$ 行,第 $i$ 行给出第 $i$ 个物品的合成配方，格式如下： 首先一个正整数 $p$ ($0\leq p \leq 1$)代表物品的种类

• $p=0$ 代表该物品为原材料，则后面一个正整数 $t$ ($1\leq t \leq 10^5$) 代表获取一个该物品需要花费的时间。
• $p=1$ 代表该物品为合成产物，则后面一个正整数 $t$ ($1\leq t \leq n$) 代表该配方中原料的数量，接着给出 $t$ 组 ($x_i$,$a_i$) 数对($1\leq x_i \leq 10^5$，$1\leq a_i \leq n$),代表第 $i$ 个原料的数量与种类。

Output

共 $t$ 行 每行一个整数，表示 agKc 合成这件物品的最短耗时，同时若最短耗时大于 $10^9$ ，请输出 Impossible 。

Sample Input

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

Sample Output

6
0
13

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）