Description

Now here is the problem: Think of the sky as a number line. On this number line there are many stars, each with a position $X_i$ and a brightness $B_i$. Multiple stars may share the same position. The range a window can see is given by a parameter $W$, and the stars we see also include those on the window’s boundaries. Find the maximum possible sum of brightness of the stars visible after adjusting the position of the window.

Input Format

One line with $N, W$, the number of stars and the width of the window.

Each of the next $N$ lines contains $X_i$ and $B_i$, the coordinate and brightness of a star.

Output Format

One number, the maximum total brightness of the visible stars.

6 3
1 2
2 4
3 8
4 4
5 2
1000 1

16

Hint

Sample explanation:

Constraints:

• For $10\%$ of the testdata, $W = 0$ (no boundary).
• For $40\%$ of the testdata, $W \leq 1000$.
• For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $0 \leq W \leq 10^5$, $1 \leq X_i \leq 10^5$, $1 \leq B_i \leq 100$.
• Except for the case $W = 0$, $W$ is an odd integer $\geq 3$.

Translated by ChatGPT 5