2025 天梯赛筛选赛

Problem D. 塞车不插队(30分)

塞车插队是很过分的行为。

已知有 n 辆车,m 种颜值。其中从前往后数第 i 辆车的颜值为 a_i

由于插队行为,导致原本的车辆顺序被打乱了,并且打乱顺序后导致这些车的颜值也发生了变化。现在从前向后数第 i 辆车的颜值为 b_i

小w知道存在一个整数 x,满足 c_i = (a_i + x) \mod m,并且将 c_i 以某种方式排序之后,可以得到 b_i

小w想知道 x 的最小值是多少。

输入

第一行两个整数 nm,表示车的数量和颜值的种类。

第二行 n 个整数,表示 a_i

第三行 n 个整数,表示 b_i

输出

一个整数,表示 x 的最小值。数据保证有解。

样例

标准输入 复制文本
4 3
0 0 2 1
2 0 1 1
标准输出 复制文本
1
标准输入 复制文本
3 2
0 0 0
1 1 1
标准输出 复制文本
1
标准输入 复制文本
5 10
0 0 0 1 2
2 1 0 0 0
标准输出 复制文本
0

提示

数据范围

对于 50\% 的数据,n \leq 50

对于 100\% 的数据,1 \leq n \leq 10000 \leq a_i, b_i, m \leq 10^9

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 453
通过 113

A B C D E F G H