骑士游戏 ### 题目描述 长期的宅男生活中，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$ 个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。 其中，$2 \le N \le 2 \times 10^5,1 \le R_i,\sum R_i \le 10^6,1 \le K_i,S_i \le 5 \times 10^{14}$。 ### 输出描述 输出一行一个整数，表示最少需要的体力值。 ### 输入输出样例 #### 示例 1 >输入 ``` txt 4 4 27 3 2 3 2 3 5 1 2 1 13 2 4 2 5 6 1 2 ``` >输出 ``` txt 26 ```