D. City Renewal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The group has arrived in Austin! There they discover that the city council needs their help. However, they are very busy attending concerts so they've asked you to do this for them!

The city council of Austin is planning a large-scale urban renewal project along its East–West highway. There are $$$n$$$ proposed building expansions, each located at a distinct integer coordinate along the highway. Every proposal has an associated profit value. However, due to zoning regulations, any two chosen expansions must be sufficiently far apart. Specifically, if you approve the expansion at coordinate $$$x$$$, then you may not approve another expansion within distance $$$d$$$ of $$$x$$$.

Formally, you are given:

  • An integer $$$n$$$ — the number of proposed expansions.
  • An integer $$$d$$$ — the minimum required spacing between approved expansions.
  • For each $$$i$$$ from $$$1$$$ to $$$n$$$:
    • An integer $$$x_i$$$ (the coordinate of the $$$i$$$-th proposal).
    • An integer $$$p_i$$$ (the profit from the $$$i$$$-th proposal).
All coordinates $$$x_i$$$ are pairwise distinct, and you want to choose a subset of these expansions so that no two chosen expansions are within $$$d$$$ of each other. Formally, for any two chosen expansions at coordinates $$$x_i$$$ and $$$x_j$$$, you must have $$$|x_i - x_j| \ge d$$$. Your goal is to maximize the total profit from the chosen expansions.
Input

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq d \leq 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$p_i$$$ ($$$1 \leq x_i \leq 10^9$$$, $$$1 \leq p_i \leq 10^9$$$).

It is guaranteed that all $$$x_i$$$ are distinct.

Output

Print a single integer: the maximum total profit you can achieve while respecting the spacing constraint.

Example
Input
6 2
3 1
5 4
7 1
8 2
9 1
12 5
Output
12