TopCoder

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

30.0% (15/50)

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

3 1 10 100
2 5
3 8
1 7

Sample Output

8

Hints

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

Problem 1612 rejudge, 感謝 poloo5582!!

Problem Source

原TIOJ1612 / Problem Setter: suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536
2 5000 65536 65536
3 5000 65536 65536
4 5000 65536 65536
5 5000 65536 65536
6 5000 65536 65536
7 5000 65536 65536
8 5000 65536 65536
9 5000 65536 65536
10 5000 65536 65536
11 5000 65536 65536
12 5000 65536 65536
13 5000 65536 65536
14 5000 65536 65536
15 5000 65536 65536
16 5000 65536 65536
17 5000 65536 65536
18 5000 65536 65536
19 5000 65536 65536