[R15E]扫地机器人 - 代码源竞赛平台

时空限制

2S/512M

数轴上有 $n$ 个扫地机器人和 $m$ 个垃圾， $i$ 号机器人的初始坐标为 $a_i$ ，第 $i$ 个垃圾的坐标为 $b_i$ 。

扫地机器人每秒的移动距离为 $1$ ，分为三个种类：

$1$ 类机器人只能向左移动，也就是说如果现在有一个 $1$ 类机器人位于坐标 $x$ ，那么 $1$ 秒后它位于坐标 $x-1$ ；
$2$ 类机器人只能向右移动，也就是说如果现在有一个 $2$ 类机器人位于坐标 $x$ ，那么 $1$ 秒后它位于坐标 $x+1$ ；
$3$ 类机器人可以自己选择向左或向右移动，随时可以改变方向且改变方向不花时间，也就是说如果现在有一个 $3$ 类机器人位于坐标 $x$ ，那么 $1$ 秒后它可能位于坐标 $x-1$ 或坐标 $x+1$ 。

一个垃圾被任意一个扫地机器人经过时会被清理，清理垃圾不花时间。多个扫地机器人可以同时位于一个坐标。

求清理所有垃圾最少需要花多少秒。数据保证至少有一个 $3$ 类机器人。

第一行包含两个整数 $n,m$ ，分别表示扫地机器人的数量和垃圾的数量。

第二行包含 $n$ 个整数 $a_i$ ，分别表示每个扫地机器人的初始坐标。

第三行包含 $n$ 个整数 $k_i$ ，分别表示每个扫地机器人的类型。

第四行包含 $m$ 个整数 $b_i$ ，分别表示每个垃圾的坐标。

输出一个整数表示清理所有垃圾最少需要花多少秒。

3 6
3 9 14
3 2 3
6 15 1 9 8 4

其中一种方案为：

$1$ 号机器人 $0\sim 2$ 秒向左移动到达坐标 $1$ ， $2\sim 7$ 秒向右移动到达坐标 $6$ ，过程中可以清理到垃圾： $1,3,6$ ；
$2$ 号机器人 $0\sim 7$ 秒向右移动到达坐标 $15$ ，过程中可以清理到垃圾： $2,4$ ；
$3$ 号机器人 $0\sim 7$ 秒向左移动到达坐标 $7$ ，过程中可以清理到垃圾： $4,5$ 。

所有的垃圾都在 $7$ 秒内被清理了。

1 2
500000000
3
1000000000 1

1499999998

对于 $20\%$ 的数据， $n\leq 1000$ ， $m\leq 2000$ ， $k_1=3$ ，且对于 $i>1$ 有 $1\leq k_i\leq 2$ 。

对于 $40\%$ 的数据， $k_1=3$ ，且对于 $i>1$ 有 $1\leq k_i\leq 2$ 。

另有 $20\%$ 的数据， $k_i=3$ 。

对于 $100\%$ 的数据， $1\leq n\leq 10^5$ ， $1\leq m\leq 2\times 10^5$ ， $1\leq a_i,b_i\leq 10^{18}$ ， $1\leq k_i\leq 3$ 。数据保证至少有一个 $i$ 满足 $k_i=3$ 。