← 返回题目列表

AtCoder · abc232_g

G. 模最短路径

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个有向图 N 顶点,称为 Vertex 1,顶点 2, \ldots,顶点 N.

对于每对整数,使得 1 \leq i, j \leq N 和 i \neq j,有一条来自 Vertex 的有向边 i 到顶点 j 的重量 (A_i + B_j) \bmod M。 (这里, x \bmod y 表示当 x 除以 y.)

除上述以外没有其他边缘。

打印距顶点的最短距离 1 到顶点 N,即从 Vertex 开始的路径中边的最小可能总权重 1 到顶点 N.

约束

  • 2 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • 0 \leq A_i, B_j < M
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

下面, i \rightarrow j 表示来自 Vertex 的有向边 i 到顶点 j.
让我们考虑一下路径 1 \rightarrow 3 \rightarrow 2 \rightarrow 4.

  • 边缘 1\rightarrow 3 称重 (A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2,
  • 边缘 3 \rightarrow 2 称重 (A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1,
  • 边缘 2\rightarrow 4 称重 (A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0.

因此,该路径中边的总权重为 2 + 1 + 0 = 3.
这是从顶点开始的路径的最小可能总和 1 到顶点 N.


示例输入 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