题目描述

Anton and his friends are planning a vacation together. They have already chosen the location; however, the dates are harder to agree on.

All $N$ friends have submitted in advance the days they plan to take off work. Friend $i$ originally scheduled their time off from day $L_i$ to day $R_i$, inclusive. To maximize the time they can spend together, each friend may adjust their time off by shifting it earlier or later. Specifically, the $i$-th friend can choose an integer $d_i$ and move their time off to the interval $[L_i + d_i, R_i + d_i]$. A positive $d_i$ means taking time off later than originally planned, a negative $d_i$ means earlier, and $d_i = 0$ means keeping the original schedule.

The friends recognize that their bosses will not like the disruption caused by their changes. Therefore, they will only move their days off in a way such that the total movement of the intervals does not exceed some integer $K$. Formally, they have to satisfy $|d_0| + |d_1| + \cdots + |d_{N-1}| \leq K$.

Help the friends figure out the maximum number of days all of them can be together if they change their schedules optimally.

Implementation details

You should implement the function plan_vacation:

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

• $N$: the number of friends
• $L$: a vector of $N$ positive integers, each of which denotes the first day off originally scheduled for that friend;
• $R$: a vector of $N$ positive integers, each of which denotes the last day off originally scheduled for that friend;
• $K$: the maximum allowed value of $|d_0| + |d_1| + \cdots + |d_{N-1}|$.

This function will be called once for each test. It has to return the maximum number of days all friends can be together or 0 if that isn't possible at all.

输入格式

The input format is the following:

• line 1: two integers – the values of $N$ and $K$.
• lines 2 to $N + 1$: two integers – $L_i$ and $R_i$.

输出格式

The output format is the following:

• line 1: one integer – the return value of the call.

3 3
1 3
5 9
2 5

2

提示

Example

Consider the following call:

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

The friends have requested the following intervals of days off: $[1, 3]$, $[5, 9]$, $[2, 5]$. Therefore, friend 0 can move their time off to 2 days later and friend 1 their time off to 1 day earlier to get $[3, 5]$, $[4, 8]$, $[2, 5]$. Then, all friends would be available on day 4 and day 5, which results in 2 days in common. It can be proven that they can't do better with $K = 3$. Therefore, the function should return 2.

Constraints

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

Subtasks

Subtask	Points	Required subtasks	Additional constraints
0		-	The example.
1	7		$K = 0$
2	11	1	$K \leq 1$
3	6	-	$K = 10^{18}$
4	13	0	$N \leq 10^4$, $L_i \leq 10$, $R_i \leq 10$
5	18		$N \leq 10^3$
6	29	0, 4, 5	$N \leq 10^5$
7	16	0 - 6	-