Description

Anton 和他的朋友们计划一起去度假。地点已经选好，但具体日期很难统一。

共有 $N$ 位朋友，每人事先提交了自己计划请假的日期。第 $i$ 位朋友原本安排的请假区间为从第 $L_i$ 天到第 $R_i$ 天（含两端）。为了最大化大家在一起的时间，每位朋友可以将自己的请假区间整体向前或向后平移：具体地，第 $i$ 位朋友可以选择一个整数 $d_i$，把他的请假区间移动为 $[L_i + d_i,\, R_i + d_i]$。其中，$d_i > 0$ 表示比原计划更晚请假，$d_i < 0$ 表示更早请假，$d_i = 0$ 表示保持原计划不变。

朋友们也意识到领导不会喜欢他们频繁调整，因此他们只会在总位移不超过某个整数 $K$ 的前提下移动自己的请假区间。形式化地，他们必须满足

请帮助他们在最优调整的情况下，计算所有人能够共同在一起的天数的最大值。

实现细节

你需要实现函数 plan_vacation：

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

• $N$：朋友人数；
• $L$：长度为 $N$ 的正整数向量，第 $i$ 个数表示该朋友原计划请假的第一天；
• $R$：长度为 $N$ 的正整数向量，第 $i$ 个数表示该朋友原计划请假的最后一天；
• $K$：允许的总位移上限，即 $|d_0| + |d_1| + \cdots + |d_{N-1}|$ 的最大值。

该函数在每个测试中调用一次。它需要返回所有朋友能共同在一起的最大天数；如果完全无法做到让所有人同日有空，则返回 $0$。

Input Format

输入格式如下：

• 第 1 行：两个整数——$N$ 与 $K$；
• 第 $2$ 到第 $N+1$ 行：每行两个整数——$L_i$ 与 $R_i$。

Output Format

输出格式如下：

• 第 1 行：一个整数——函数的返回值。

3 3
1 3
5 9
2 5

2

Hint

示例

考虑如下调用：

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 \le N \le 500\,000$
• $1 \le L_i \le R_i \le 10^9$
• $0 \le K \le 10^{18}$

子任务

翻译由 ChatGPT-5 完成。