게으른 백곰

더운 여름날 동물원 백곰 앨버트는 너무 더워서 움직이기 싫다. 사육사들이 얼음 양동이를 가져왔고, 앨버트가 최소한만 움직여 최대한 많은 얼음으로 더위를 싣고 싶다.

일차원 직선 위에 N(1 ≤ N ≤ 100000)개의 얼음 양동이가 xi(0 ≤ xi ≤ 1,000,000)에 놓여 있고, 각 양동이에는 gi(1 ≤ gi ≤ 10,000)만큼 얼음이 들어 있다. 앨버트가 한 위치에 앉으면 좌우로 K(1 ≤ K ≤ 2,000,000) 이내의 양동이에 닿을 수 있다. 양동이가 있는 좌표에도 앉을 수 있다. 모든 양동이 위치는 서로 다르다.

앨버트가 최적의 위치를 골랐을 때 닿을 수 있는 얼음 양의 합(최댓값)을 구하라.

첫 줄에 정수 N, K. 다음 N줄에 각 양동이의 gi와 xi가 공백으로 구분되어 주어진다.

앨버트가 고른 위치에서 K 이내에 닿을 수 있는 얼음의 합의 최댓값을 출력한다.