1612 . Problem F 小朋友上樓梯 (JUMPUP)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

94.4% (34/36)

Submission's AC Ratio

31.7% (65/205)

Tags

Description

還記得小朋友下樓梯嗎 ?

但是這次你的任務變了。一開始時，你在高度為0的位置，而你要往上跳到高度為X的位置。

在高度0到X之間，總共有n個樓梯，第i個樓梯位在Xi的位置，且樓梯上有Vi的經驗值。任兩個樓梯都不會在同樣的高度。

此外，當你在該樓梯上落腳時，就可以得到該樓梯上的經驗值。

很不幸的，由於有時間限制，你必須要剛好在k ( k ≤ n ) 個樓梯上落腳。請問你最多能得到多少經驗值 ?

對了，由於等級限制，你不能一次往上跳超過D的高度。

還有，即使有個樓梯正好在 X 的位置，也不一定要踩喔。

Input Format

輸入的第一行有四個正整數，以空白隔開，依序代表n、k、X、D。1 ≤ k ≤ n ≤ 3,000，1 ≤ X, D < 231。

接下來有n行，每一行都有兩個正整數。第i+1行的兩個正整數依序代表Xi、Vi。1 ≤ Xi ≤ X，1 ≤ Vi < 500,000。

Output Format

請輸出一個正整數，代表最多能獲得的經驗值。測資中保證不會出現無解的情況。

Sample Input 1

3 1 10 100
2 5
3 8
1 7

Sample Output 1

8

Hints

在20筆測資當中，有17筆 n≦500。

Problem 1612 rejudge, 感謝 poloo5582！！

Problem Source

原TIOJ1612 / Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 5
20 19 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11
11 5000 65536 262144 12
12 5000 65536 262144 13
13 5000 65536 262144 14
14 5000 65536 262144 15
15 5000 65536 262144 16
16 5000 65536 262144 17
17 5000 65536 262144 18
18 5000 65536 262144 19
19 5000 65536 262144 20
Submit
Back to Top