题目描述

在游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。 游戏世界中一共有$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$。 【数据规模】 对于100%的数据，$2≤N≤2×10^5，1≤R_i,ΣR_i≤10^6，1≤K_i,S_i≤5×10^{14}$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。