Score : $600$ points

问题描述

我们有一个有向图，包含 $N$ 个顶点，分别称为顶点 $1$, 顶点 $2$, $\ldots$, 顶点 $N$。

对于每一对整数 $i$ 和 $j$，满足 $1 \leq i, j \leq N$ 且 $i \neq j$，存在一条从顶点 $i$ 到顶点 $j$ 的有向边，其权重为 $(A_i + B_j) \mod M$。（此处，$x \bmod y$ 表示 $x$ 除以 $y$ 后的余数。）

除此之外没有其他边。

请输出从顶点 $1$ 到顶点 $N$ 的最短距离，即从顶点 $1$ 到顶点 $N$ 的路径中所有边的最小可能总权重。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a directed graph with $N$ vertices, called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$.

For each pair of integers such that $1 \leq i, j \leq N$ and $i \neq j$, there is a directed edge from Vertex $i$ to Vertex $j$ of weight $(A_i + B_j) \bmod M$. (Here, $x \bmod y$ denotes the remainder when $x$ is divided by $y$.)

There is no edge other than the above.

Print the shortest distance from Vertex $1$ to Vertex $N$, that is, the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i, B_j < M$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

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

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

Output

Print the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.

Sample Input 1

4 12
10 11 6 0
8 7 4 1

Sample Output 1

3

Below, $i \rightarrow j$ denotes the directed edge from Vertex $i$ to Vertex $j$.
Let us consider the path $1$ $\rightarrow$ $3$ $\rightarrow$ $2$ $\rightarrow$ $4$.

• Edge $1\rightarrow 3$ weighs $(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2$,
• Edge $3 \rightarrow 2$ weighs $(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1$,
• Edge $2\rightarrow 4$ weighs $(A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0$.

Thus, the total weight of the edges in this path is $2 + 1 + 0 = 3$.
This is the minimum possible sum for a path from Vertex $1$ to Vertex $N$.

Sample Input 2

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

Sample Output 2

462

update @ 2024/3/10 10:07:39