小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$个人的最小不耐烦程度之和。

样例一

input

1
0 2426 8707

output

0

样例二

input

4
0 1929 401
1 7233 960
1 3564 9106
2 4746 182

output

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

下载

样例数据下载