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. P
i = C
i = 1.
Subtask 2 (17%): 1 ≤ K ≤ N ≤ 100. 1 ≤ L, P
i, C
i ≤ 100.
Subtask 3 (25%): 1 ≤ K ≤ N ≤ 500. 1 ≤ L, P
i, C
i ≤ 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