#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

Guan is a nutritionist looking for clients. He has a total of *N* potential clients, each with a calorie count *C _{i}* and a price

*P*that the client would pay Guan if Guan chose to take this client up.

_{i}
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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 9 | 20 | 1s | 64MB | Minimum |

2 | 17 | 40 | 1s | 64MB | Minimum |

3 | 25 | 60 | 1s | 64MB | Minimum |

4 | 49 | 80 | 1s | 64MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o nutritionist -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512