题目描述

给你一个长度为 $n$ 的数组 $points$ 和一个整数 $k$ 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 $points[i] = [x_i, y_i]$ ，并且在 $1 <= i < j <= points.length$ 的前提下， $x_i < x_j$ 总成立。

请你找出 $y_i + y_j + |x_i - x_j|$ 的 最大值，其中 $|x_i - x_j| <= k$ 且 $1 <= i < j <= points.length$。

题目测试数据保证至少存在一对能够满足 $|x_i - x_j| <= k$ 的点。

输入格式

第一行两个整数 $n$ 和 $k$；

接下来的 $n$ 行，每行两个数表示第 $i$ 个点的坐标 $x,y$。

输出格式

一行一个整数表示答案。

示例 1：

4 1
1 3
2 0
5 10
6 -10

4

解释：

前两个点满足 |xi - xj| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。

没有其他满足条件的点，所以返回 4 和 1 中最大的那个。

示例 2：

3 3
0 0
3 0
9 2

3

解释：

只有前两个点满足 |xi - xj| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。

提示：

• $2 <= points.length <= 10^5$
• $points[i].length == 2$
• $-10^8 <= points[i][0], points[i][1] <= 10^8$
• $0 <= k <= 2 * 10^8$
• 对于所有的$1 <= i < j <= points.length$ ，$points[i][0] < points[j][0]$ 都成立。也就是说，$x_i$ 是严格递增的。

SOURCE

1499. 满足不等式的最大值