← 返回题目列表

Codeforces · 830/A

A. 办公室钥匙

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

一条直线上有 n 个人和 k 个钥匙。每个人都想到达位于线路上的办公室。为此,他需要带着钥匙到达某个地点,拿走钥匙然后去办公室。钥匙一旦被某人拿走,其他人就无法拿走。

您需要确定所有 n 个人携带钥匙到达办公室所需的最短时间。假设人们每 1 秒移动一个单位距离。如果两个人同时拿到一把钥匙,则只有其中一个人能拿走钥匙。一个人可以用钥匙穿过一个点而不需要拿钥匙。

输入

第一行包含三个整数 n、k 和 p (1 ≤ n ≤ 1 000, n ≤ k ≤ 2 000, 1 ≤ p ≤ 109) — 人数、钥匙数量和办公地点。

第二行包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 人们最初所处的位置。位置以任意顺序给出。

第三行包含 k 个不同的整数 b1, b2, ..., bk (1 ≤ bj ≤ 109) — 键的位置。位置以任意顺序给出。

请注意,同一点上不能有超过一个人或多个钥匙。人和钥匙可以位于同一点。

输出

打印所有 n 携带钥匙到达办公室所需的最短时间(以秒为单位)。

示例

输入 #1

2 4 50
20 100
60 10 40 80

输出 #1

50

输入 #2

1 2 10
11
15 7

输出 #2

7

注意

在第一个示例中,位于点 20 的人应该拿走位于点 40 的钥匙并带着它前往位于点 50 的办公室。他花了 30 秒。位于点 100 的人可以拿着位于点 80 的钥匙并带着它去办公室。他花了50秒。因此,50 秒后,每个人都拿着钥匙到了办公室。