Rohan, as Simon's protégé, has been tasked with food fair robbery from clubs in order to raise funds. In front of him are \(N\) food fair stalls, indexed from \(1\) to \(N\). The \(i\)th stall contains \(c_{i}\) tickets, but if they see any of the previous \(p_{i}\) stalls being robbed, they will close up and it will be impossible to rob them.

Trying to impress Simon as much as he can, help Rohan find the maximum number of tickets he can rob from the stalls. You may assume Rohan can only travel from stall \(1\) to stall \(N\), in that order.

Constraints

\(1 \le c_{i} \le 10^9\)

\(0 \le p_{i} < i \le N\)

Subtask 1 [30%]

\(1 \le N \le 10^3\)

Subtask 2 [70%]

\(1 \le N \le 10^6\)

Input Specification

The first line contains \(N\).

The following \(N\) lines contain two integers, \(c_{i}\) and \(p_{i}\), with the \(i\)th line describing the \(i\)th stall.

Output Specification

Output one integer, the maximum number of tickets Rohan can take.

Sample Input 1

5
2 0
3 0
2 1
3 1
4 3

Sample Output 1

8

Sample Input 2

4
1 0
1 0
1 0
4 3

Sample Output 2

4