一个城镇的所有电力都来自太阳能和水力发电大坝。这些能源并不总是最可靠的，因为阳光和水的量每天都会有很大波动。幸运的是，大坝有一个大型水库，可以储存水以平衡每天的电力供应。

你将获得未来 $n$ 天的信息。在第 $i$ 天，太阳能发电站产生 $s_i$ 单位的电力。同时，有 $w_i$ 单位的水流入水库。每一单位水可以转化为一单位电力，你可以决定转化多少水以及在水库中留下多少水。然而，水库最多只能容纳 $r$ 单位的水，因此在每天结束时，水库中的水量不能超过 $r$。第一天开始时，水库是空的。

第一天开始时，水库中没有储存水。在最后一天结束时，大坝将进行维护，必须排空。换句话说，在 $n$ 天内流入大坝的所有水最终都必须转化为电力。

设 $e_i$ 为第 $i$ 天产生的电量。注意 $e_i = s_i + r_i$，其中 $r_i$ 是你在第 $i$ 天从水库中转化的水量。你的任务是找到 $\max_i(e_i) - \min_i(e_i)$ 的最小值。

输入格式

第一行包含两个整数 $n$ 和 $r$ ($1 \le n \le 10^5$, $1 \le r \le 10^9$)，分别表示天数和水库的容量。

接下来的 $n$ 行，每行包含两个整数 $s_i$ 和 $w_i$ ($0 \le s_i, w_i \le 10^9$)，分别表示第 $i$ 天太阳能发电站产生的电量和流入水库的水量。

输出格式

输出 $\max_i(e_i) - \min_i(e_i)$ 的最小值。

样例

样例输入 1

3 1
4 2
2 0
5 1

样例输出 1

3