Modulo Shortest Path

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一个包含 $N$ 个顶点的有向图，顶点编号为 $1$ 到 $N$。

对于每一组满足 $1\leq i,j\leq N$ 且 $i\neq j$ 的整数对 $(i,j)$，存在一条从顶点 $i$ 指向顶点 $j$ 的有向边，其权值为 $(A_i+B_j)\bmod M$。除此之外图中没有其他边。

请输出从顶点 $1$ 到顶点 $N$ 的最短距离，即路径上所有边权之和的最小值。

输入格式

输入以如下格式给出：

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

$B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出一个整数，表示从顶点 $1$ 到顶点 $N$ 的最短距离。

样例输入 1

4 12
10 11 6 0
8 7 4 1

样例输出 1

3

样例输入 2

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

样例输出 2

462

样例解释

对于样例 1，路径 $1\to3\to2\to4$ 的三条边权分别是 $2,1,0$，总和为 $3$，且不存在更短路径。

数据范围

• $2\leq N\leq 2\times 10^5$
• $2\leq M\leq 10^9$
• $0\leq A_i,B_i<M$
• 所有输入值均为整数。