有 N 个物品，编号 1 到 N。每个物品 i 有一个价格 P_i、等级 L_i 和若干替代关系 (T, V)，表示如果已经拥有物品 T，则可以用 V 金币购买物品 i。

目标是获得物品 1。可以直接用 P_i 购买物品 i，也可以通过替代关系用更低价格购买。

限制：交易过程中，所有参与交易的物品主人的等级，最大值与最小值之差不能超过 M。

求获得物品 1 所需的最少金币数。

第一行两个整数 M, N。

接下来 N 行，第 i 行描述物品 i：

• 三个整数 P, L, X：价格、等级、替代品数量。
• 接下来 X 行，每行两个整数 T, V：拥有 T 后，i 的价格为 V。

一行一个整数，表示最少金币数。

1 \le N \le 100，1 \le P \le 10000，1 \le L, M \le N，0 \le X < N。