There are n beacons on a line, the i-th at position x_i with signal strength y_i. The positions are given in strictly increasing order, and each consecutive gap is at most k (so x_{i+1} - x_i <= k).
For any pair of beacons i < j with x_j - x_i <= k, their combined signal is y_i + y_j + (x_j - x_i). Report the maximum combined signal over all such pairs. Because consecutive positions differ by at most k, at least one valid pair always exists.
Input format
Line 1: two integers n and k.
Next n lines: two integers x_i and y_i, with x strictly increasing and consecutive gaps at most k.
Output format
A single integer: the maximum combined signal over all valid pairs.
Constraints
- 2 <= n <= 100000
- 1 <= k <= 1000000000
- -1000000000 <= x_i, y_i <= 1000000000; x strictly increasing; consecutive gaps at most k.