UOJ Logo Universal Online Judge

UOJ

#624. 【统一省选2021 A/B卷】卡牌游戏

Attachment Statistics

Alice 有 $n$ 张卡牌,第 $i$($1 \le i \le n$)张卡牌的正面有数字 $a_i$,背面有数字 $b_i$,初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 $m$ 张卡牌翻面,即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 $n$ 个数字的极差(最大值与最小值的差)尽量小。请你帮 Alice 算一算极差的最小值是多少。

输入格式

第一行,两个正整数 $n, m$,代表卡牌张数与至多翻面张数。

第二行,$n$ 个正整数,第 $i$ 个数字表示 $a_i$。

第二行,$n$ 个正整数,第 $i$ 个数字表示 $b_i$。

数据保证卡牌上的 $2n$ 个数字互不相同,且卡牌按照 $a_i$ 升序给出。

输出格式

仅一行,一个整数,表示答案。

样例一

input

6 3
8 11 13 14 16 19
10 18 2 3 6 7

output

8

explanation

最优方案之一:将第 $1, 5, 6$ 张卡牌翻面,最终朝上的数字依次为 $10, 11, 13, 14, 6, 7$,极差为 $14 - 6 = 8$。

样例二

见附加文件中 ex_card2.inex_card2.ans

样例三

见附加文件中 ex_card3.inex_card3.ans

限制与约定

对于所有测试数据:$3 \le n \le 10^6, 1 \le m \lt n, 1 \le a_i, b_i \le {10}^9$。

每个测试点的具体限制见下表:

测试点编号 $n \leq$ 特殊限制
$1 \sim 2$ $10$
$3 \sim 4$ $500$
$5 \sim 6$ $5\times 10^5$ $m \leq 1000$
$7$ $1 \times 10^5$
$8$ $4 \times {10}^5$
$9$ $7 \times {10}^5$
$10$ $1 \times {10}^6$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载