Marcus is a LLM power user, in particular he has become quite adept with setting up and managing agentic workflows to replace his lazy teammates. Marcus sets up intricate chains of AI processes, where each process takes time to produce some data, and then spawns potentially multiple subprocesses to perform even more work.

Marcus has designed such a workflow to make promotional posters for an upcoming event. He has setup each process and knows how long each one is going to relate, and also which processes are children of others. Marcus's computer can run as many processes in parallel as it likes, but it cannot start running a process until it's parent process has completed. While his agents work, Marcus is going to go for a megawalk outside, but he wants to know how long he should go out for.

Can you calculate how long it will be until Marcus's entire agentic workflow is complete?

Input

The first input contains a single integer ~n~ (~1 \leq n \leq 10^4~), the number of processes which comprise Marcus's agentic workflow. Each process is labelled ~1~ through ~n~.

The next ~n~ lines each contain information about one of these processes. The ~i~th line contains two integers ~p_i, c_i~ (~1 \leq p_i \leq i~, ~0 \leq c_i \leq 10^5~), the parent process label and the duration of the ~i~th process. Note that ~p_i = i~ is possible and indicates that a process has no parent. Due to perfect parallelism, this means that the process may be started instantly. Each other process may only be started once its parent is complete.

Output

Output a single integer ~t~, the total amount of time required for all processes to complete.

Example

Input 1

6
1 3
1 1
2 2
1 5
5 1
5 2

Output 1

8

The processes form a structure that can be seen in this image:

After ~3~ seconds, process ~1~ will be complete. Then, ~5~ seconds after, process ~4~ will be complete. At this stage, all other processes will already have been completed if we start them instantly after their parent completes (and start all parentless processes immediately at the start). Thus ~8~ seconds is needed.

Input 2

5
1 2
1 1
2 3
3 2
4 1

Output 2

9

In this case, all processes depend on the previous process, so we cannot parallelise everything. We must wait for each process to complete in order, which takes ~2+1+3+2+1=9~ seconds.