atcoder#ABC232G. [ABC232G] Modulo Shortest Path

[ABC232G] Modulo Shortest Path

Score : 600600 points

Problem Statement

We have a directed graph with NN vertices, called Vertex 11, Vertex 22, \ldots, Vertex NN.

For each pair of integers such that 1i,jN1 \leq i, j \leq N and iji \neq j, there is a directed edge from Vertex ii to Vertex jj of weight (Ai+Bj)modM(A_i + B_j) \bmod M. (Here, xmodyx \bmod y denotes the remainder when xx is divided by yy.)

There is no edge other than the above.

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

Constraints

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 2M1092 \leq M \leq 10^9
  • 0Ai,Bj<M0 \leq A_i, B_j < M
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN MM

A1A_1 A2A_2 \ldots ANA_N

B1B_1 B2B_2 \ldots BNB_N

Output

Print the minimum possible total weight of the edges in a path from Vertex 11 to Vertex NN.

4 12
10 11 6 0
8 7 4 1
3

Below, iji \rightarrow j denotes the directed edge from Vertex ii to Vertex jj. Let us consider the path 11 \rightarrow 33 \rightarrow 22 \rightarrow 44.

  • Edge 131\rightarrow 3 weighs (A1+B3)modM=(10+4)mod12=2(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2,
  • Edge 323 \rightarrow 2 weighs (A3+B2)modM=(6+7)mod12=1(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1,
  • Edge 242\rightarrow 4 weighs (A2+B4)modM=(11+1)mod12=0(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=32 + 1 + 0 = 3. This is the minimum possible sum for a path from Vertex 11 to Vertex NN.

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