题目描述

神话-黑悟空中，天命人可以用棍子和棒子攻击，而消耗不同魔法值。

例如：现在在打第一个$boss$黑风老妖：

采用棍子打$boss$，打败后$boss$会变出一些分身$boss$，注意这个$boss$可能经过若干次棍子击打后变回一个或更多同样的$boss$；而采用棒子攻击就可以直接打死而不会产生分身。

神话-黑悟空中一共有$N$种不同的$boss$，分别由$1$到$N$编号，现在面对$1$号$boss$，天命人想知道，要杀死所有神话-黑悟空游戏中的$boss$，最少要使用多少魔法值？

输入格式

第一行包含一个整数$N$。

接下来$N$行，每行描述一个$boss$的信息；

其中第$i$行包含若干个整数，前三个整数为$S_i，K_i$和$R_i$，表示对于$i$号$boss$，棍子攻击需要消耗$S_i$的魔法值，棒子攻击需要消耗Ki的魔法值，同时$i$号$boss$死亡后会产生$R_i$个新的$boss$。表示一个新出现的$boss$编号。同一编号的$boss$可以出现多个。

输出格式

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

样例输入1

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

样例输出1

26

提示

首先用消耗4点魔法用棍子攻击，然后出现的$boss$编号是$2$，$2$和$3$。花费$10$点魔法用棒子攻击杀死两个编号为$2$的$boss$。剩下$3$号$boss$花费$1$点魔法进行棍子攻击。剩下$boss$编号是$2$和$4$。最后花费$11$点魔法用棒子攻击将这两只$boss$彻底杀死。一共花费的魔法是$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}$。