← 返回题目列表

Codeforces · 343/C

C. 读取时间

中文机器翻译题面 查看原题

疯狂科学家迈克不使用慢速硬盘。他改造的硬盘不是只有一个,而是有n个不同的磁头,可以并行读取数据。

从侧面看,迈克的硬盘驱动器是无尽的磁道阵列。阵列的磁道从左到右用整数编号,从1开始。在初始状态下,第i个读头位于磁道号hi上方。对于每个读取头,硬盘驱动器的固件可以将读取头向右或向左精确移动一个磁道,或者将其保留在当前磁道上。操作过程中,每个头的运动不会影响其他头的运动:头可以改变它们的相对顺序;任何轨道上方都可以有多个读取头。如果至少有一个磁头访问过该磁道,则该磁道被视为已读。特别地,编号为h1、h2、...、hn的所有磁道在操作开始时已被读取。

Mike 需要读取编号为 p1、p2、...、pm 的 m 个不同磁道上的数据。确定硬盘驱动器固件移动磁头并读取所有给定磁道所需的最短时间。请注意,也可以读取任意数量的其他磁道。

输入

输入的第一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 105) — 相应的磁盘头数量和要读取的磁道数量。第二行包含 n 个不同的整数 hi,按升序排列 (1 ≤ hi ≤ 1010,hi < hi + 1) — 头部的初始位置。第三行包含 m 个不同的整数 pi,按升序排列 (1 ≤ pi ≤ 1010, pi < pi + 1) - 要读取的磁道数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。建议使用 cin、cout 流或 %I64d 说明符。

输出

打印单个数字 — 读取所有所需磁道所需的最短时间(以秒为单位)。

示例

输入 #1

3 4
2 5 6
1 3 6 8

输出 #1

2

输入 #2

3 3
1 2 3
1 2 3

输出 #2

0

输入 #3

1 2
165
142 200

输出 #3

81

注意

第一次测试与图吻合。在这种情况下,可以通过以下方式在 2 秒内读取给定的曲目:

1. 在第一秒内将第一个头向左移动并让它停留在那里;
2.将第二个头向左移动两次;
3、将第三个磁头向右移动两次(注意一开始就已经读取了第6磁道)。

由于第 3 个磁头与第 8 个磁道的距离为 2,因此无法在 1 秒内读取磁道。