Anton 和他的朋友们正在计划一起度假。他们已经选好了地点，但日期很难达成一致。

所有 $N$ 个朋友都提前提交了他们计划请假的日期。朋友 $i$ 最初计划的请假时间是从第 $L_i$ 天到第 $R_i$ 天（闭区间）。为了最大化他们能在一起的时间，每个朋友都可以通过将请假时间提前或推迟来调整自己的假期。具体来说，第 $i$ 个朋友可以选择一个整数 $d_i$，并将他们的请假时间移动到区间 $[L_i + d_i, R_i + d_i]$。正的 $d_i$ 表示比原计划晚请假，负的 $d_i$ 表示早请假，$d_i = 0$ 表示保持原计划。

朋友们意识到他们的老板不会喜欢这种变动带来的混乱。因此，他们移动请假天数的方式必须满足所有区间移动的总量不超过某个整数 $K$。形式化地，他们必须满足：

$$|d_0| + |d_1| + \dots + |d_{N-1}| \le K$$

帮助朋友们计算如果他们以最优方式调整日程，所有人能在一起的最大天数。

实现细节

你应该实现函数 plan_vacation：

int plan_vacation(int N, std::vector<int> L, std::vector<int> R, long long K)

• N：朋友的数量。
• L：一个包含 $N$ 个正整数的 std::vector，每个元素表示该朋友原计划请假的第一天。
• R：一个包含 $N$ 个正整数的 std::vector，每个元素表示该朋友原计划请假的最后一天。
• K：$|d_0| + |d_1| + \dots + |d_{N-1}|$ 的最大允许值。

该函数在每个测试用例中会被调用一次。它必须返回所有人能在一起的最大天数，如果根本不可能在一起，则返回 0。

数据范围

• $1 \le N \le 500\,000$
• $1 \le L_i \le R_i \le 10^9$
• $0 \le K \le 10^{18}$

子任务

样例

输入样例 1

3 3
1 3
5 9
2 5

输出样例 1

2

说明

考虑以下调用：

plan_vacation(3, {1, 5, 2}, {3, 9, 5}, 3)

朋友们请求的请假区间分别为：$[1, 3]$，$[5, 9]$，$[2, 5]$。因此，朋友 0 可以将他们的请假时间向后移动 2 天，朋友 1 将他们的请假时间向前移动 1 天，从而得到 $[3, 5]$，$[4, 8]$，$[2, 5]$。这样，所有朋友在第 4 天和第 5 天都有空，从而有 2 天的共同时间。可以证明，在 $K = 3$ 的情况下，无法获得更好的结果。因此，函数应该返回 2。

评测程序示例

输入格式如下：

• 第 1 行：两个整数，表示 $N$ 和 $K$ 的值。
• 第 2 到 $N + 1$ 行：两个整数，表示 $L_i$ 和 $R_i$。

输出格式如下：

• 第 1 行：一个整数，表示函数调用的返回值。