問題文

N 個のブロックが並べられており、左から順に 1, 2, \cdots, N と番号が付けられています。
あなたは、以下の 2 種類の操作を何回か行うことで、すべてのブロックを取り除きたいです。

• 今ある中で 一番左 のブロックを取り除く。
• 今ある中で 一番右 のブロックを取り除く。

ブロック i (i = 1, 2, \cdots, N) をブロック P_i より先に取り除いた場合、A_i 点が得られます。
合計得点としてあり得る最大値を出力するプログラムを作成してください。

制約

• 2 \leq N \leq 2000
• 1 \leq P_i \leq N
• P_i \neq i
• 1 \leq A_i \leq 100
• 入力はすべて整数

入力例 1

4
4 20
3 30
2 40
1 10

出力例 1

60

ブロック 1 \to ブロック 4 \to ブロック 3 \to ブロック 2 の順番に取り除けば良いです。

入力例 2

8
8 100
7 100
6 100
5 100
4 100
3 100
2 100
1 100

出力例 2

400