[R50C]截断加法 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定两个长度为 $n$ 的数组 $a$ 和 $b$，以及两个正整数 $D$ 和 $k$（保证对于所有的 $i$，都有 $a_i \leq D$）。

你需要找一个最小的非负整数 $x$ 来满足下面的条件：

• 令 $c_i = \min(D , a_i + x)$，至少有 $k$ 个位置 $i$ 满足 $c_i \ge b_i$。

求满足条件的最小 $x$，如果不存在满足条件的 $x$，请输出 -1。

格式

输入格式

第一行包含三个正整数 $n$、$D$ 和 $k$，分别表示数组的长度、给定的常数 $D$ 以及要求满足条件的最小数量 $k$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $a$ 的值。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示数组 $b$ 的值。

输出格式

输出一行一个整数，表示满足条件的最小非负整数 $x$。如果没有满足条件的 $x$，输出 -1。

样例

样例输入 #1

3 10 2
2 5 8
6 12 9

样例输出 #1

4

样例输入 #2

3 10 2
2 7 8
6 6 9

样例输出 #2

1

样例输入 #3

3 10 3
2 7 8
6 12 9

样例输出 #3

-1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$50$	$2000$
$2$	$50$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^5$，$1 \leq D \leq 10^9$，$1 \leq a_i, b_i \leq 10^9$，$a_i \leq D$。