TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

小風有 n 個堅果,每個堅果有他的重量 ai 以及他們所代表的價值 wi。小風想從中選出一些堅果 i1,i2,i3,im 堆成堅果塔,為了使堅果塔穩定,每個堅果重量必須不小於上方兩個堅果的重量,也就是 3km,aikaik1+aik2。請求出小風能堆出最大可能的堅果價值 wik 總和。

Input Format

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

之後 n 行每行兩個數字,表示 aiwi

  • 2n5000
  • 1ai,wi109

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