2943: 骑士游戏 [knight]（day1-3）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
【故事背景】
长期的宅男生活中，JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中，JYY 一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统 bug，并不保证这一点）。游戏世界中一共有 N 种不同的怪兽，分别由 1 到 N 编号，现在 1 号怪兽入侵村庄了，JYY 想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？
长期的宅男生活中，JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中，JYY 一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统 bug，并不保证这一点）。游戏世界中一共有 N 种不同的怪兽，分别由 1 到 N 编号，现在 1 号怪兽入侵村庄了，JYY 想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？
Input
第一行包含一个整数 N。
接下来 N 行，每行描述一个怪兽的信息；
其中第 i 行包含若干个整数，前三个整数为Si，Ki和Ri ，表示对于 i 号怪兽，普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时 i 号怪兽死亡后会产生Ri 个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
接下来 N 行，每行描述一个怪兽的信息；
其中第 i 行包含若干个整数，前三个整数为Si，Ki和Ri ，表示对于 i 号怪兽，普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时 i 号怪兽死亡后会产生Ri 个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
Output
输出一行一个整数，表示最少需要的体力值。
Sample Input Copy
4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2
Sample Output Copy
26
HINT
【样例说明】
首先用消耗 4 点体力用普通攻击，然后出现的怪兽编号是 2，2 和 3。花费10 点体力用法术攻击杀死两个编号为 2 的怪兽。剩下 3 号怪兽花费 1 点体力进行普通攻击。此时村庄里的怪兽编号是 2 和 4。最后花费 11 点体力用法术攻击将这两只怪兽彻底杀死。
一共花费的体力是 4+5+5+1+5+6=26。
【数据规模】
对于 20%的数据满足 N≤5；
对于 50%的数据满足N≤300 ；
对于 100%的数据满足2≤N≤2x10^5,1≤Ri，
Ri≤10^6,1≤Ki,Si≤5x10^14。
首先用消耗 4 点体力用普通攻击，然后出现的怪兽编号是 2，2 和 3。花费10 点体力用法术攻击杀死两个编号为 2 的怪兽。剩下 3 号怪兽花费 1 点体力进行普通攻击。此时村庄里的怪兽编号是 2 和 4。最后花费 11 点体力用法术攻击将这两只怪兽彻底杀死。
一共花费的体力是 4+5+5+1+5+6=26。
【数据规模】
对于 20%的数据满足 N≤5；
对于 50%的数据满足N≤300 ；
对于 100%的数据满足2≤N≤2x10^5,1≤Ri，
Ri≤10^6,1≤Ki,Si≤5x10^14。