#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct picture{
int h;
int money;
}H[300100];
int ptr = -1;
int N, S;
int D[300100];
bool cmp(picture A, picture B){
return A.h < B.h;
}
int Fd_max(int HM){
if(HM < H[0].h) return ptr = -1;
if(ptr == -1) ptr = 0;
for(int i = ptr; i < N; i++){
if(HM < H[i].h) return ptr = i - 1;
}
}
int max(int a, int b){
return a < b? b : a;
}
void Fl_dyn(){
D[0] = H[0].money;
for(int i = 1; i < N; i++){
int X = Fd_max(H[i].h - S);
if(X == -1) D[i] = max(D[i - 1], H[i].h);
else {
int x = ptr;
D[i] = max(D[i - 1], D[x] + H[i].money);
}
}
}
int main()
{
scanf("%d %d", &N, &S);
for(int i = 0; i < N; i++){
scanf("%d %d", &H[i].h, &H[i].money);
}
sort(H, H + N, cmp);
Fl_dyn();
printf("%d\n", D[N - 1]);
return 0;
}
//선생님이 강의해주신대로 코드를 짜 봤는데요... 어디가 틀려서 30점일까요?
조회 : 2,618
