← 返回题目列表

AtCoder · tessoku_book_u

A21. 方块游戏

中文机器翻译题面 查看原题

配点: 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