Birthday Presents

Interview

Time limit2sMemory limit512 MB

Summary

Pick a subset of presents whose price range is below D, maximizing total satisfaction.

Level: Medium5 of 10
Topics: Sorting, Sliding window, Two pointers, Prefix sum
Solved: No attempts yet

Problem

Today is Kangmin's birthday. Kangmin has N friends, and every friend prepared one birthday present for him. Each present has a price P and a satisfaction value V. P is the price of the present, and V is a number for how happy Kangmin is when he receives that present.

Kangmin wants every present. The trouble is that if the price of one friend's present differs from the price of another friend's present by D or more, the friend who gave the cheaper present may feel sorry. Kangmin's own happiness matters to him, but he does not want a birthday present to make a friend feel sorry, so after some thought he decided to accept presents from only some of his friends.

Find the largest total satisfaction Kangmin can feel when he picks presents so that nobody feels sorry. Nobody feels sorry exactly when the price difference between the most expensive and the cheapest accepted present is smaller than D.

Input

The first line contains the number of friends N and the smallest price difference D that makes a friend feel sorry. ( $1 \le N \le 100\,000$ , $1 \le D \le 1\,000\,000\,000$ )

Each of the next N lines contains the price P and the satisfaction value V of one present. ( $0 \le P \le 1\,000\,000\,000$ , $0 \le V \le 1\,000\,000\,001$ )

Output

Print the maximum total satisfaction Kangmin can feel.

Examples2

Example 1
Input
```
4 2
13 10
10 20
11 30
12 40
```
Expected output
```
70
```
Example 2
Input
```
3 5
0 100
5 100
4 1
```
Expected output
```
101
```