Little U has been overwhelmed with work lately because a crowd of people wants him to debug their code. There are $n$ people in total who need his help. They have been working on a difficult problem from the National Training Team (which requires algorithms like persistent Top cactus), but none of them have managed to get their code working. They are numbered $1, 2, \ldots, n$ and are lined up in increasing order of their IDs.

Little U wants to divide them into batches and debug their code from front to back (i.e., from the smallest ID to the largest). Each batch must consist of a contiguous segment of people. The time required for the $i$-th person to debug their code is $t_i$. A batch of people can only leave once everyone in that batch has finished debugging. In other words, the time a batch occupies the room is the maximum of the debugging times of everyone in that batch.

Because students are easily influenced by each other, for any batch where the person with the largest ID is $i$, they cannot be in the same batch as the person with ID $l_i$. If $l_i = 0$, it means there is no such restriction.

Each student also has an impatience index. For every unit of time the $i$-th student waits, their impatience increases by $w_i$. The waiting time is defined as the duration from when they line up until the student enters the room, which is the sum of the time spent in the room by all batches of students ahead of them.

Little U wants them to successfully debug this problem while minimizing the total sum of impatience. However, he is busy helping them and has delegated this task to you.

Input

The first line contains a positive integer $n$, representing the number of people.

The next $n$ lines each contain three non-negative integers $l_i, t_i, w_i$, with meanings as described in the problem statement.

It is guaranteed that $0 \leq l_i < i$.

Output

A single line representing the minimum total sum of impatience for the $n$ people.

Examples

Input 1

1
0 2426 8707

Output 1

0

Input 2

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

Output 2

21084798

Constraints

This problem has 5 subtasks. For all data, $0 \leq t_i, w_i \leq 10^9$, and the final answer does not exceed $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$, and $w_i, t_i$ are generated uniformly at random within a certain range

Subtask 4 (12 pts): $1 \leq n \leq 100\,000$, and $t_i \leq t_{i+1}$

Subtask 5 (51 pts): $1 \leq n \leq 100\,000$