ダイクストラ法を用いることで頂点 \(1\) から頂点 \(N\) への最短経路を求めることができますが、問題文中のグラフ（ \(G\) とおく）は \(N\) 個の頂点と \(\Theta(N^2)\) 本の有向辺を持つため、\(\Theta(N^2\log N)\) の計算時間かかり、実行制限時間に間に合わせることは絶望的です。

その対策として、\(G\) と等価で頂点数と辺数がともに \(\mathrm{O}(N)\) であるような有向グラフ \(G''\) を構築し、\(G''\) に対してダイクストラ法を適用する方針を取ります。

まず \(G\) に対して、次のような有向グラフ \(G'\) を考えます。

• \(G\) の \(N\) 個の頂点 \(1, 2, \ldots, N\) に加えて、\(M\) 個の頂点 \(\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{M-1}\) を持つ。

• \(k = 0, 1, \ldots, M-1\) のそれぞれについて、重み \(1\) の有向辺 \(\overline{k} \rightarrow \overline{k+1}\) をもつ。ただし、\(\overline{M}\) は \(\overline{0}\) とみなす。

• \(i = 1, 2, \ldots, N\) のそれぞれについて、重み \(0\) の有向辺 \(i \rightarrow \overline{(-A_i) \bmod M}\) を持つ。

• \(i = 1, 2, \ldots, N\) のそれぞれについて、重み \(0\) の有向辺 \(\overline{B_i} \rightarrow i\) を持つ。

入力例 \(1\) の \(G\) と、それに対する \(G'\) をそれぞれ次の \(2\) つの図に示します。

\(G\) の有向辺 \(s \rightarrow t\) と「 \(G'\) 上のパス \(s \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_l \rightarrow t\) で下記の \(2\) つをともに満たすもの」は \(1\) 対 \(1\) に対応します。

• \(s, v_0, v_1, \ldots, v_l, t\) は相異なる
• \(i = 1, 2, \ldots, l\) のすべてについて、\(v_i \not\in \lbrace \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{M-1} \rbrace\)

具体的には、\(G\) の有向辺 \(s \rightarrow t\) が、\(G'\)上のパス \(s \rightarrow \overline{(-A_s) \bmod M} \rightarrow \overline{(-A_s+1) \bmod M} \rightarrow \overline{(-A_s+2) \bmod M} \rightarrow \cdots \rightarrow \overline{B_t} \rightarrow t\) と対応します。

例えば入力例 \(1\) においては、次の \(2\) つの図に示すように、\(G\) の有向辺 \(3 \rightarrow 4\) が、\(G'\) 上のパス \(3 \rightarrow \overline{6} \rightarrow \overline{7} \rightarrow \overline{8} \rightarrow \overline{9} \rightarrow \overline{10} \rightarrow \overline{11} \rightarrow \overline{0} \rightarrow \overline{1} \rightarrow 4\) と対応します。

さらに、\(G\) の有向辺とそれに対応する \(G'\) 上のパスの重みは等しいです。

よって、\(G\) 上での頂点 \(1\) から頂点 \(N\) への最短パスの重みと、\(G'\) 上での頂点 \(1\) から頂点 \(N\) への最短パスの重みは等しいです。 そのため、本問題は \(G'\) 上での最短経路問題に帰着できます。

\(G'\) は \(N+M\) 個の頂点を持っているため、このままではやはり実行制限時間に間に合わせることは絶望的ですが、 次の図に示すように重み \(1\) の辺をまとめ、必要な頂点だけを残したグラフ \(G''\) を考えると、頂点数と辺数を \(\mathrm{O}(N)\) に削減することができます。

形式的には、グラフ \(G''\) は次のようになります。

まず、

\(\mathcal{A}_1 := \lbrace \overline{(-A_i) \bmod M} : i = 1, 2, \ldots, N \rbrace\)

\(\mathcal{A}_2 := \lbrace \overline{B_i} : i = 1, 2, \ldots, N \rbrace\)

\(\mathcal{A} := \mathcal{A}_1 \cup \mathcal{A}_2\)

とします。このとき、

• \(G''\) の頂点集合は \(\lbrace 1, 2, \ldots, N\rbrace \cup \mathcal{A}\) です。

• また、\(i = 1, 2, \ldots, N\) のそれぞれについて、重み \(0\) の有向辺 \(\overline{B_i} \rightarrow i\) と重み \(0\) の有向辺 \(i \rightarrow \overline{(-A_i) \bmod M}\) があります。

• さらに、それぞれの \(\overline{x} \in \mathcal{A}\) に対して、重み \((y_x-x) \mod M\) の有向辺 \(\overline{x} \rightarrow \overline{y_x}\) があります。 ここで、\(\overline{y_x}\) は \((y-x) \bmod M\) が最小となる \(\overline{y} \in \mathcal{A} \setminus \lbrace \overline{x}\rbrace\) です。

このグラフ \(G''\) に対してダイクストラ法を用いることによって、本問題を \(\mathrm{O}(N\log N)\) 時間で解くことができます。