You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

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$，分别表示每个垃圾的坐标。

输出格式

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

样例

样例输入 #1

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

样例输出 #1

7

样例解释 #1

其中一种方案为：

• $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$ 秒内被清理了。

样例输入 #2

1 2
500000000
3
1000000000 1

样例输出 #2

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$。