nutritionist

Problem Description

Guan is a nutritionist looking for clients. He has a total of N potential clients, each with a calorie count Ci and a price Pi that the client would pay Guan if Guan chose to take this client up.

However, Guan faces a very big problem. His company insists that he "specialises" in a field, so the difference between the maximum calorie intake of all his clients and the minimum calorie intake of all his clients must not exceed L. Also, Guan can only take up a maximum of K clients. Help Guan earn the maximum amount of money possible.

Subtasks

Subtask 1 (9%): 1 ≤ K ≤ N ≤ 100. 1 ≤ L ≤ 100. Pi = Ci = 1.
Subtask 2 (17%): 1 ≤ K ≤ N ≤ 100. 1 ≤ L, Pi, Ci ≤ 100.
Subtask 3 (25%): 1 ≤ K ≤ N ≤ 500. 1 ≤ L, Pi, Ci ≤ 500.
Subtask 4 (49%): 1 ≤ K ≤ N ≤ 200 000. No integer in the input will be more than 32-bit.

Input

The first line of input will contain three integers, N, K and L.
The next N lines will contain two integers each, referring to the calorie count and the price of the client respectively.

Output

The output should contain one integer, the maximum amount of money Guan can get.

Sample Input 1

7 3 6
3 7
5 9
7 3
11 2
13 6
14 8
15 3

Sample Output 1

19

Submitting to 'nutritionist'


You're not logged in! Click here to login


Submitting .cpp to 'nutritionist'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 2
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 9
2 17
3 25
4 49
5 0