题目描述

有 $N$ 只蚂蚁在一个圆圈上。圆圈有 $L$ 个位置，按顺时针方向从 $1$ 到 $L$ 编号，其中位置 $L$ 与位置 $1$ 相邻。蚂蚁们从不同的位置出发，并且希望到达不同的目标位置。为此，每一秒内每只蚂蚁可以保持不动，或者沿着圆圈移动到相邻的位置（顺时针或逆时针方向）。

任意两只蚂蚁不能在同一时间处于圆圈上的同一位置，即使在位置之间的移动过程中也不允许相遇。例如，假设在一秒内一只蚂蚁从位置 $1$ 顺时针移动到位置 $2$，则在这一秒内，其他蚂蚁不能进行以下任何操作：

• 在位置 $2$ 保持不动（蚂蚁会在位置 $2$ 相遇）。
• 从位置 $3$ 逆时针移动到位置 $2$（蚂蚁会在位置 $2$ 相遇）。
• 从位置 $2$ 逆时针移动到位置 $1$（蚂蚁会在位置 $1$ 和 $2$ 之间的路径上相遇）。

请判断是否可能让所有蚂蚁都到达它们的目标位置，若可能，求出所需的最少秒数。也就是说，找出最小的 $t$，使得经过 $t$ 秒后，每只蚂蚁都能够位于它的目标位置。

输入格式

第一行包含两个整数 $N$（$1 \le N \le 1000$）和 $L$（$1 \le L \le 10^9$），分别表示蚂蚁的数量以及圆圈上的位置数。

第二行包含 $N$ 个互不相同的整数 $A_1, A_2, \ldots, A_N$（对于 $i = 1, 2, \ldots, N$ 有 $1 \le A_i \le L$），其中 $A_i$ 是第 $i$ 只蚂蚁的初始位置。

第三行包含 $N$ 个互不相同的整数 $B_1, B_2, \ldots, B_N$（对于 $i = 1, 2, \ldots, N$ 有 $1 \le B_i \le L$），其中 $B_i$ 是第 $i$ 只蚂蚁的目标位置。

输出格式

输出一行，包含一个整数，表示所有蚂蚁到达目标位置所需的最少时间；如果不可能，则输出字符 “*”（星号）。

2 2
2 1
2 1

0

2 2
1 2
2 1

1

1 10
1
7

4

3 5
1 3 2
5 2 4

*

3 5
1 3 2
4 2 5

2

提示

样例 1 解释：

两只蚂蚁一开始就已在各自的目标位置，因此答案为 $0$。

样例 2 解释：

两只蚂蚁可以同时顺时针或逆时针移动，仅需 $1$ 秒即到达各自的目标。

样例 5 解释：

三只蚂蚁可以全部逆时针移动，其中第二只蚂蚁在原地停留一秒。

翻译由 DeepSeek V4 Pro 完成