糖果

题目描述

一天，小 $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/out，ex_candy3.in/out，ex_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}$