F2-来自过去的求助（pilgrimage）

题目背景

我是Lsxszc，现在正在出比赛，但是我出不了高难度的题目，于是我经常去找kkkw寻求帮助。但是kkkw经常打破第四面墙，导致我没灵感写有意思的题目背景和后记了。

于是我打算回到过去，在过去的记忆中挑一道好的F题，也不去麻烦kkkw了。

般若波罗蜜！

这是？机房，正好是中午，kkkw和助教和同学都还在食堂吃饭，正好行动！我走到我的电脑前，打开显示器，映入眼帘的是一道熟悉的图论题。

这是kkkw集训结束也没有讲完的题目，说实话我在集训时根本看不懂正解，集训结束后就没怎么看过这题了，现在还不知道怎么写。我看了看时间，正好是11:50，我需要快一点解决这一道题，不然助教就回来了。

嘿！我知道你在看，快来帮我！

题目描述

在浩瀚无垠的“艾德拉”星系，散布着 N 颗拥有生命的星球，编号从 1 到 N。星球之间由一个古老而神秘的“星门”网络连接，使得星际旅行成为可能。你是一位年轻的探险家，立志完成一场传说中的“星尘之旅”——从你的母星（1号星球）出发，穿越星海，最终抵达位于星系中心的圣地（N号星球）。

每一次星门跳跃的成本都遵循着一种奇特的宇宙法则。这个法则与三个因素有关：

1. 出发星球的“星门共鸣频率” (A)：每颗星球 i 都有一个独一无二的共鸣频率 $A_i$。
2. 抵达星球的“行星谐振值” (B)：每颗星球 j 也有一个独特的谐振值 $B_j$。
3. 宇宙的“以太模量” (M)：一个作用于整个星系的恒定能量常数。

从星球 i 跳跃到星球 j 所需的“以太水晶”成本计算公式为：

其中，$x \pmod M$ 表示 $x$ 除以 $M$ 的余数。

你的飞船上装载着一份星图，上面记录了所有星球的共鸣频率 $A_i$ 和谐振值 $B_j$。你可以在任意星球之间进行跳跃，也可以多次访问同一颗星球。你的任务是规划出一条从 1 号星球到 N 号星球的路线，使得总的“以太水晶”花费最少。

输入格式

输入的第一行包含两个整数 N 和 M。 第二行包含 N 个整数 $A_1, A_2, \dots, A_N$。 第三行包含 N 个整数 $B_1, B_2, \dots, B_N$。

输出格式

输出一个整数，表示从 1 号星球旅行到 N 号星球所需的最小总花费。

输入输出样例 #1

输入 #1

4 12
10 11 6 0
8 7 4 1

输出 #1

3

说明/提示

样例解释

一种可能的最佳路线是 $1 \to 3 \to 2 \to 4$。

• 从 $1 \to 3$ 的花费: $(A_1 + B_3) \pmod{12} = (10 + 4) \pmod{12} = 14 \pmod{12} = 2$。
• 从 $3 \to 2$ 的花费: $(A_3 + B_2) \pmod{12} = (6 + 7) \pmod{12} = 13 \pmod{12} = 1$。
• 从 $2 \to 4$ 的花费: $(A_2 + B_4) \pmod{12} = (11 + 1) \pmod{12} = 12 \pmod{12} = 0$。 总花费为 $2 + 1 + 0 = 3$。这是可以达成的最小花费。

数据范围与部分分

对于全部数据：

• $2 \le N \le 2 \times 10^5$
• $2 \le M \le 10^9$
• $0 \le A_i, B_j < M$

后记

原来是这样$\dots$

谢谢了，现在回忆起来，那段时光真的是快乐呀。可惜 $\dots$ 没有可惜。

“此情可待成追忆，只是当时已惘然。”

谢谢你，kkkw！