【集训队作业2018】line
小U最近锅多如狗，因为有一堆的人要找他调代码。一共有$n$ 个人要找他办事 。他们做了一道国家集训队的一道神题，要用到可持久化 Top cactus 等算法，但是他们都没有把代码调出来。他们分别编号为 $1, 2, \ldots, n$，且编号从小到大排成一列。
小U想把他们按编号分成各批，然后从前往后（即编号从小到大）分批调代码。其中每一批人的编号是连续的一段。第 $i$ 个人调出代码需要 $t_i$ 个单位时间。而每一批蒟蒻需要把代码都调好，才能出来。也就是说，他们占用教室的时间为每个人调代码所需时间的最大值。
由于同学Gayfriends之间容易互相影响，每一批蒟蒻内编号最大的人，设编号为 $i$，不能与编号为 $l_i$ 的人在同一批，否则这一批的代码会调不出来。如果 $l_i = 0$，就意味着没有这个限制这位同学是个纯洁的好孩子。
而每位蒟蒻都会有不耐烦指数。第 $i$ 位蒟蒻每等待一个单位时间，他的不耐烦程度就会增加 $w_i$。等待时间指的是从他们排好队到这个蒟蒻进教室为止的这段时间，也就是排在他前面的每一批蒟蒻占用教室时间之和。
现在小U想让他们成功调出这道神题，并且不耐烦程度的和最小。可是他忙着帮助他们，就把这个任务交给了你。
输入格式
第一行一个正整数 $n$，表示人数。
接下来 $n$ 行每行三个非负整数 $l_i, t_i, w_i$，意义如题面所述。
保证 $0 \leq l_i \lt i$。
输出格式
仅一行，表示$n$个人的最小不耐烦程度之和。
1
0 2426 8707
0
4
0 1929 401
1 7233 960
1 3564 9106
2 4746 182
21084798
限制与约定
本题有 5 个子任务。对于所有数据，有 $0 \leq t_i, w_i \leq 10^9$，且最终答案不大于 $10^{18}$。
Subtask 1 (9 pts): $1 \leq n \leq 10$；
Subtask 2 (10 pts): $1 \leq n \leq 2\,000$；
Subtask 3 (18 pts): $1 \leq n \leq 100\,000$ 且 $w_i$，$t_i$ 均为一定范围内等概率随机生成；
Subtask 4 (12 pts): $1 \leq n \leq 100\,000$ 且 $t_i \leq t_{i+1}$；
Subtask 5 (51 pts): $1 \leq n \leq 100\,000$。
时间限制：$3\mathtt{s}$
空间限制：$512\mathtt{MB}$