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.

4 3
1 3
2 0
4 5
5 1

11

2 5
0 4
2 6

12