Lazy Polar Bear

On a hot summer day, zoo polar bear Albert is too lazy to move. Keepers bring ice buckets, and Albert wants to cool off with as much ice as possible while moving as little as possible.

There are N ice buckets (1 ≤ N ≤ 100,000) on a line at distinct coordinates xi (0 ≤ xi ≤ 1,000,000). Bucket i holds gi units of ice (1 ≤ gi ≤ 10,000). After Albert sits at one position, he can reach any bucket within distance K (1 ≤ K ≤ 2,000,000) to the left or right. He may sit on a bucket coordinate.

Find the maximum total ice he can reach when he chooses the best position.

Line 1: integers N and K. Each of the next N lines: integers gi and xi for one bucket.

Print the maximum sum of ice reachable within distance K of Albert's chosen position.