#2225. 「AHOI2014」骑士游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

长期的宅男生活中,JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。

在这个游戏中,JYY 一共有两种攻击方式,一种是普通攻击,一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统 bug,并不保证这一点)。

游戏世界中一共有 N 种不同的怪兽,分别由 1 N 编号,现在 1 号怪兽入侵村庄了,JYY 想知道,最少花费多少体力值才能将所有入侵村庄的怪兽全部杀死呢?

输入格式

第一行包含一个整数 N
接下来 N 行,每行描述一种怪兽的信息;
其中第 i 行包含若干个整数,前三个整数为 S_i K_i R_i ,表示对于 i 号怪兽,普通攻击需要消耗 S_i 的体力,法术攻击需要消耗 K_i 的体力,同时 i 号怪兽死亡后会产生 R_i 个新的怪兽。其后的 R_i 个整数分别表示每个新出现的怪兽编号。同一编号的怪兽可以出现多个。

输出格式

输出一行一个整数,表示最少需要的体力值。

样例

样例输入

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

样例输出

26

样例说明

首先消耗 4 点体力用普通攻击,然后出现的怪兽编号是 2, 2 3 。花费 10 点体力用法术攻击杀死两个编号为 2 的怪兽。剩下 3 号怪兽花费 1 点体力进行普通攻击。此时村庄里的怪兽编号是 2 4 。最后花费 11 点体力用法术攻击将这两只怪兽彻底杀死。一共花费的体力是 4+5+5+1+5+6=26

数据范围与提示

对于所有数据, 2 \leq N \leq 2 \times 10^5,\ 1 \leq R_i,\sum R_i \leq 10^6,\ 1 \leq K_i,S_i \leq 5 \times 10^{14}