{"problem":{"name":"Modulo Shortest Path","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc232_g"},"statements":[{"statement_type":"Markdown","content":"We have a directed graph with $N$ vertices, called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$.\nFor 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$.)\nThere is no edge other than the above.\nPrint 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$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $2 \\leq M \\leq 10^9$\n*   $0 \\leq A_i, B_j < M$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$B_1$ $B_2$ $\\ldots$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc232_g","tags":[],"sample_group":[["4 12\n10 11 6 0\n8 7 4 1","3\n\nBelow, $i \\rightarrow j$ denotes the directed edge from Vertex $i$ to Vertex $j$.  \nLet us consider the path $1$ $\\rightarrow$ $3$ $\\rightarrow$ $2$ $\\rightarrow$ $4$.\n\n*   Edge $1\\rightarrow 3$ weighs $(A_1 + B_3) \\bmod M = (10 + 4) \\bmod 12 = 2$,\n*   Edge $3 \\rightarrow 2$ weighs $(A_3 + B_2) \\bmod M = (6 + 7) \\bmod 12 = 1$,\n*   Edge $2\\rightarrow 4$ weighs $(A_2 + B_4) \\bmod M = (11 + 1) \\bmod 12 = 0$.\n\nThus, the total weight of the edges in this path is $2 + 1 + 0 = 3$.  \nThis is the minimum possible sum for a path from Vertex $1$ to Vertex $N$."],["10 1000\n785 934 671 520 794 168 586 667 411 332\n363 763 40 425 524 311 139 875 548 198","462"]],"created_at":"2026-03-03 11:01:14"}}