망원경 회전 계획

문제

한 천문대에서 하룻밤 동안의 관측 계획을 세우려 한다. 관측 후보는 N개이고, 시간 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 후보는 하늘의 한 직선 위에서 위치 x_i를 가리키며, 관측하면 성과 w_i를 얻는다. w_i는 음수일 수도 있는데, 이는 장비 소모 비용이 얻는 자료의 가치보다 큰 경우이다. 망원경은 처음에 위치 0을 향하고 있다. 후보 중 일부를 번호가 증가하는 순서로 골라 차례대로 관측한다. 망원경은 한 번 회전할 때 위치를 최대 K만큼만 바꿀 수 있다. 즉 현재 향한 위치가 c이고 다음에 관측할 후보의 위치가 x이면 |x - c| ≤ K일 때만 그 후보를 관측할 수 있고, 관측 뒤에는 망원경이 x를 향한다. 첫 관측도 처음 위치 0에서 같은 규칙을 따른다. 서로 다른 후보가 같은 위치를 가리킬 수 있으며 이때 회전 거리는 0이다. 고른 후보들의 성과 합이 최대가 되도록 하고 그 최댓값을 구하라. 아무것도 관측하지 않는 것도 가능하며 이때 합은 0이다.

입력

첫째 줄에 N과 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ K ≤ 10^9) 이어지는 N개의 줄에 i번째 후보의 x_i와 w_i가 공백으로 구분되어 주어진다. (|x_i| ≤ 10^9, |w_i| ≤ 10^6) 모든 값은 정수이다.

출력

성과 합의 최댓값을 한 줄에 출력한다.

5 3
2 5
10 20
5 -1
8 4
11 7

15

3 1
5 10
-5 -3
6 -2

0

출처: Devin.KR 자체 제작