配点: 1000 点
問題文
N 块从左侧开始排列。
它的编号为 1, 2, \cdots, N 。
您想要通过多次执行以下两种类型的操作来删除所有块。
- 在当下 删除 一番左 块。
- 在当下 删除 一番右 块。
块
我们称之为 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
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N P_1 A_1 P_2 A_2 \cdots P_N A_N
出力
请以整数形式输出最大总分。 您可以按照
入力例 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