TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

小風有 $n$ 個堅果,每個堅果有他的重量 $a_i$ 以及他們所代表的價值 $w_i$。小風想從中選出一些堅果 $i_1, i_2, i_3, \ldots i_m$ 堆成堅果塔,為了使堅果塔穩定,每個堅果重量必須不小於上方兩個堅果的重量,也就是 $\forall 3 \leq k \leq m, a_{i_k} \geq a_{i_{k-1}} + a_{i_{k-2}}$。請求出小風能堆出最大可能的堅果價值 $w_{i_k}$ 總和。

Input Format

第一行有一個正整數 $n$,代表堅果有幾個。

之後 $n$ 行每行兩個數字,表示 $a_i$ 和 $w_i$。

  • $2\leq n\leq 5000$
  • $1\leq a_i,w_i \leq 10^ 9$

Output Format

輸出一個數字代表答案。

Sample Input 1

3
1 3
2 7
1 9

Sample Output 1

19

Hints

Problem Source

IOICamp 2020 Day5 pL

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2