城市规划者计划在城市中建造 $N$ 个工厂，城市里共有 $M$ 家商店。每个工厂可以选择建造或保持在规划阶段。

每家商店都需要一组特定的工厂才能运营。如果商店 $j$ 所需的所有工厂都已建成，该商店将获得 $proj_j$ 单位的即时一次性利润。一旦工厂建成，它将生产足够的产品来支持所有依赖它的商店。

建造第 $i$ 个工厂需要 $pay_i$ 单位的投资，并且需要 $t_i$ 天。两个或多个工厂可以同时建造，因此建造多个工厂所需的时间为它们各自建造时间 $t_i$ 的最大值。

城市规划者有足够的资源建造所有工厂，但他们希望获得净利润。具体来说，他们希望选择并建造一个工厂子集，使得所服务商店的总利润减去所建工厂的总成本至少为 $L$ 单位，或者确定这是不可能的。

首先，找出使得在 $t$ 天内获得至少 $L$ 单位利润成为可能的最少天数 $t$。在此基础上，找出在 $t$ 天内可以获得的最大利润 $p$。

输入格式

输入的第一行包含三个整数 $N$、$M$ 和 $L$：可能的工厂数量、商店数量和所需利润 ($1 \le N, M \le 200, 1 \le L \le 10^9$)。

接下来 $N$ 行，每行描述一个工厂，包含两个整数 $pay_i$ 和 $t_i$：第 $i$ 个工厂的投资和建造时间 ($1 \le pay_i \le 3 \cdot 10^4, 1 \le t_i \le 10^9$)。

之后是 $M$ 行，每行描述一家商店，以一个整数 $proj_j$ 开头，表示利润 ($1 \le proj_j \le 1.2 \cdot 10^5$)。接着是一个整数 $k_j$，表示商店 $j$ 运营所需的工厂数量 ($0 \le k_j \le N$)。随后是 $k_j$ 个两两不同的整数 $plant_{j,1}, plant_{j,2}, \dots, plant_{j,k_j}$，表示商店 $j$ 运营所需的工厂索引 ($1 \le plant_{j,r} \le N$)。

输出格式

如果存在满足要求的方案，输出两个整数 $t$ 和 $p$：$t$ 必须是能够获得至少 $L$ 单位利润的最少天数，$p$ 必须是在 $t$ 天内可以获得的最大利润。

如果不存在能获得至少 $L$ 单位利润的方案，输出 “impossible”。

样例

样例输入 1

1 1 2
1 5
3 1 1

样例输出 1

5 2

样例输入 2

1 1 3
1 5
3 1 1

样例输出 2

impossible