시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 171 50 35 28.926%

문제

오늘은 강민이의 생일이다. 강민이는 친구 N명이 있는데, 각 친구는 모두 강민이를 위한 생일 선물을 하나씩 준비했다. 각각의 선물은 P와 V를 가진다. P는 해당 선물의 가격이며, V는 만족도로 해당 선물을 받았을 때 강민이가 기뻐하는 정도를 수치화한 것이다.

강민이는 모든 선물을 다 받고 싶지만, 어떤 친구가 준 선물의 가격이 다른 친구가 준 선물의 가격과 D 이상 차이 나면 더 낮은 가격의 선물을 준 친구가 미안함을 느끼게 될 수 있다. 강민이는 자신의 행복도 중요하지만, 생일선물로 친구에게 미안함을 느끼게 하고 싶지는 않다. 고심 끝에 강민이는 일부 친구들에게만 선물을 받기로 결심했다. 누구도 미안하지 않을 수 있게 선물을 받으면서, 강민이가 느낄 수 있는 만족도의 최대 합은 얼마인지 구해보자.

입력

첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P, V ≤ 1,000,000,000)가 주어진다.

출력

한 줄에 강민이가 최대 얼만큼 기뻐할 수 있는지를 출력하라.

예제 입력 1

4 2
13 10
10 20
11 30
12 40

예제 출력 1

70