题目描述

史莱姆国有 家餐厅，编号依次是 1到 n。每家餐厅的老板会有最喜欢的几家餐厅（也可能没有）。 如果你向某家餐厅的老板寻求建议，它会推荐如下的餐厅： 它自己的餐厅 它最喜欢的餐厅 它最喜欢的餐厅的老板最喜欢的餐厅 它最喜欢的餐厅的老板最喜欢的餐厅的老板最喜欢的餐厅 …依次类推…

好吃来到史莱姆国品尝美食。他决定按照如下规则拜访餐厅： 第一家餐厅可以任意选择。 此后每次选择餐厅时，必须从上一家餐厅的老板推荐的餐厅中选择。 好吃不会去此前已经去过的餐厅。 好吃可以在任意时刻结束这一流程。 每家餐厅的菜品有两种定价 Xi和 Yi。当好吃到达餐厅 i 时，老板会询问他去的上一家餐厅 j。如果好 吃尚没有去过其它餐厅，或者餐厅 j 不会被餐厅 i 的老板推荐，好吃需要支付 Yi；否则，即如果餐厅 j 在餐厅 i 的老板的推荐列表中，好吃需要支付 Xi。 设好吃最多能访问 M 家餐厅。对每个 1 到 M 中的 i，好吃想知道，如果他恰好访问了 i 家餐厅，至少需要花费多少钱。

输入格式

第一行，一个正整数 N。 接下来 N 行，每行首先输入两个正整数 Xi 和 Yi，然后输入一个非负整数 Fi，代表餐厅 i 的老板最喜欢的餐厅数量；接下来 Fi 个正整数，表示餐厅 i 最喜欢的餐厅编号。保证这些餐厅互不相同且不为 i。

输出格式

输出 M 行，第 M 行代表好吃恰好访问 家餐厅的最小花费。

输入样例

4 100 200 1 2 200 300 1 3 200 250 2 2 4 200 300 0

输出样例

200 450 650 950

数据范围

保证 1<=N<=1000 1<=Xi,Yi<=10000。 Subtask1 (10pts): N<=10 Subtask2(10pts): N<=20 Subtask3(10pts): Xi=Yi Subtask4(10pts): 餐厅 i 的老板最喜欢的餐厅编号均大于 i。 Subtask5(30pts): N<=100 Subtask6(30pts): 无特殊限制。 注：对Fi的大小没有保证