You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

长期的宅男生活中，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$ 个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。

输出格式

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

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 \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}$。