题目描述

有个图，有 $N$ 个点，点的编号为 $1$ 到 $N$。这张图上的边都是单向的，任意两点之间都有边相连。从第 $i$ 个点到第 $j$ 个点的边长为 $(X_i + Y_j) \bmod M$。其中 $M$ 是一个给定的正整数，$X_i$ 与 $Y_j$ 也是给定的两组整数。

除上述边之外，这个图没有其他的边。请求出以 $1$ 为起点，$N$ 为终点的最短路径。

输入格式

• 第一行：两个整数表示 $N$ 与 $M$
• 第二行：$N$ 个整数表示 $A_1,A_2,\dots,A_N$
• 第三行：$N$ 个整数表示 $B_1,B_2,\dots,B_N$

输出格式

4 100
10 11 6 1
8 7 4 2

12

5 1000000000
316378830 675596364 47175061 534679910 418603998
820816129 831363849 710697797 206145908 401748707

225087750

数据范围

• $30\%$ 的数据，$2\leq N\leq 1000$
• $60\%$ 的数据，$2\leq N\leq 20000$
• $100\%$ 的数据，$2\leq N\leq 300000$
• $1\leq M\leq 1,000,000,000$
• $0\leq A_i, B_i<M$

来源

改编自 ABC232G Modulo Shortest Path