Lazy Polar Bear
InterviewTime limit1sMemory limit128 MB
Choose a point on the line so the buckets within distance K of it hold the most ice in total.
- Level
Medium4 of 10
- Topics
- Sliding window, Sorting, Two pointers
- Solved
- No attempts yet
Problem
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.
Input
Line 1: integers N and K. Each of the next N lines: integers gi and xi for one bucket.
Output
Print the maximum sum of ice reachable within distance K of Albert's chosen position.