UOJ Logo

NOI.AC

2S 512MB

#30. candy

Statistics

糖果

题目描述

一天,小 $D$ 决定买一些糖果。他决定在两家不同的商店中买糖果,来体验更多的口味。

在每家商店中都有 $n$ 颗糖果,每颗糖果都有一个权值:愉悦度,代表小 $D$ 觉得这种糖果有多好吃。其中,第一家商店中的第 $i$ 颗糖果的愉悦度为 $A_i$,而第二家商店中的第 $i$ 颗糖果的愉悦度为 $B_i$。

在每家商店买的糖果会被打包到一个袋子中(可以在一家商店什么都不买,此时认为这家商店的袋子为空)。小 $D$ 回家后,因为这两个袋子外观是一样的,所以他会从两个袋子中随机选择一个.,然后吃光里面的糖果。小 $D$ 定义一种买糖果的方案的愉悦度为:吃到的糖果的愉悦度之和最小可能值

购买每颗糖果的花费均为 $W$,小 $D$ 想要最大化:买糖果的愉悦度买糖果的花费之差($x$ 与 $y$ 的差即为 $x-y$),请你帮他求出这个最大值。

输入格式

第一行两个空格隔开的整数 $n,W$,表示每家商店中的糖果数目以及每颗糖果的花费。

第二行 $n$ 个空格隔开的整数 $A_1,A_2,\cdots,A_n$,表示第一家商店中的糖果的愉悦度。

第三行 $n$ 个空格隔开的整数 $B_1,B_2,\cdots,B_n$,表示第二家商店中的糖果的愉悦度。

保证输入的 $\{A\}$ 和 $\{B\}$ 均按照从小到大的顺序排列。

输出格式

输出一行一个整数,表示这个差值的最大值。

样例输入 1

4 10
12 14 16 19
14 15 20 37

样例输出 1

5

样例解释 1

最优方案为购买第一家商店中,愉悦度为 $16$ 和 $19$ 的两颗糖果,以及第二家商店中愉悦度为 $37$ 的糖果。

如果选择第一家商店的袋子,那么愉悦度之和为 $35$;如果选择第二家商店的袋子,那么愉悦度之和为 $37$;因此这种购买方案的愉悦度为 $\min\{35,37\}=35$。

购买三颗糖果的代价为 $3\times 10=30$,所以差值为 $35-30=5$。

可以证明不存在更优的方案,所以答案为 $5$。

样例输入 2 & 3 & 4 & 5

见下发文件 ex_candy2.in/outex_candy3.in/outex_candy4.in/out 以及 ex_candy5.in/out

样例数据

数据规模与约定

本题共 $20$ 个测试数据,每个测试数据 $5$ 分。

对于前 $15\%$ 的测试数据,$n\le 5$;
对于另 $15\%$ 的测试数据,$n\le 10$;
对于另 $15\%$ 的测试数据,$n\le 50$;
对于另 $15\%$ 的测试数据,$n\le 200$;
对于另 $15\%$ 的测试数据,$n\le 1000$;
对于另 $15\%$ 的测试数据,$n\le 5000$;
对于 $100\%$ 的测试数据,$1\le n\le 10^5$,$1\le A_i,B_i,W\le 10^6$。对于任意 $1\le i\lt n$,有 $A_i\le A_{i+1}$ 且 $B_i\le B_{i+1}$。

时间限制:$2\mathtt{s}$

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