G - Modulo Shortest Path Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の有向グラフがあります。N 個の頂点はそれぞれ頂点 1、頂点 2、\ldots、頂点 N と呼ばれます。

1 \leq i, j \leq N かつ i \neq j を満たす整数の組 (i, j) それぞれに対して、 頂点 i を始点、頂点 j を終点とする重み (A_i + B_j) \bmod M の有向辺があります。 （ただし、x \bmod y は x を y で割ったあまりを表します。）

上記のほかに辺はありません。

頂点 1 から頂点 N への最短距離、すなわち、頂点 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 を始点、頂点 j を終点とする有向辺を i \rightarrow 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

Score : 600 points

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