프로그램 명: usa_lazy
제한시간: 1 초

더운 여름날이다. 암소 베시는 노곤노곤 하다. 가능한 가까운 거리에 많은 풀을 먹을 수 있는 위치에 자신을 두기를 원한다.

베시의 목초지에는 N 개의 풀 조각이 있다. 이는 직선으로 이루어져 있다. i 번째 조각에는 gi 만큼의 풀을 가지고 있다. 이 조각은 x_i 의 위치에 있다. 베시는 풀 조각이 있는 위치에 갈수 있다. 정수 위치에 갈수 있다는 것.

그가 가장 많은 풀을 먹을 수 있도록 한 지점을 선택하는 것을 도와 주는 것이 문제이다.

입력의 예에서 4 개의 지점에서 3 의 범위만큼의 풀을 취할 수 있고 각 줄 에는 풀 양과 위치가 주어진다. 그림과 같은 것이고 4 지점에 베시가 간다면 최대 11 만큼의 풀을 먹을 수 있다.

It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance.

There are N patches of grass (1 <= N <= 100,000) in Bessie's field, which we can think of as a long one-dimensional number line. The ith such patch contains g_i units of grass (1 <= g_i <= 10,000) and is located at a distinct point x_i along the field (0 <= x_i <= 1,000,000). Bessie would like to choose a point in the field as her initial location (possibly the same point as a patch of grass) so that a maximum amount of grass is within a distance of K steps from this location (1 <= K <= 2,000,000).

Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location.

입력

출력

* Line 1: The maximum amount of grass within distance K of Bessie's optimal location.

입출력 예

입력

4 3
4 7
10 15
2 2
5 1

출력

11

OUTPUT DETAILS

Bessie should locate herself at position x=4, so the grass at positions x=1, x=2, and x=7 is all within her reach. 
출처: USACO 2014 March Contest, Bronze
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]