Dijkstra’s algorithm allows us to find the shortest path from Vertex \(1\) to Vertex \(N\), but the graph in the problem statement (let us denote it by \(G\)) has \(N\) vertices and \(\Theta(N^2)\) directed edges, so it costs a total of \(\Theta(N^2\log N)\) computation time, so it is desperate that it finishes within the time limit.

Instead, we will construct a directed graph \(G''\) equivalent to \(G\) but has \(\mathrm{O}(N)\) number of vertices and edges, and adopt Dijkstra’s algorithm to \(G''\).

First, based on \(G\), consider the following directed graph \(G'\).

• In addition to \(N\) vertices \(1, 2, \ldots, N\) of \(G\), it has \(M\) vertices \(\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{M-1}\).

• For each \(k = 0, 1, \ldots, M-1\), it has a directed edge \(\overline{k} \rightarrow \overline{k+1}\) of weight \(1\). Here, \(\overline{M}\) is regarded as \(\overline{0}\).

• For each \(i = 1, 2, \ldots, N\), it has a directed edge \(i \rightarrow \overline{(-A_i) \bmod M}\) of weight \(0\).

• For each \(i = 1, 2, \ldots, N\), it has a directed edge \(\overline{B_i} \rightarrow i\) of weight \(0\).

Here are illustrations of \(G\) and corresponding \(G'\).

A directed edge \(s \rightarrow t\) on \(G\) and “a path \(s \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_l \rightarrow t\) on \(G'\) that satisfies the following two conditions” corresponds one-by-one.

• \(s, v_0, v_1, \ldots, v_l, t\) are pairwise distinct
• for any \(i = 1, 2, \ldots, l\), \(v_i \not\in \lbrace \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{M-1} \rbrace\)

Specifically, A directed edge \(s \rightarrow t\) on \(G\) corresponds to a path \(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\) on \(G'\).

For example, in Sample Input \(1\), as the two illustrations below shows, the directed edge \(3 \rightarrow 4\) of \(G\) corresponds to the path \(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\) on \(G'\).

Moreover, the weight of a directed edge on \(G\) and the weight of the corresponding path are equal.

Therefore, the weight of the shortest path from Vertex \(1\) to Vertex \(N\) on \(G\) and the weight of the shortest path from Vertex \(1\) to Vertex \(N\) are equal. Hence, the problem can be boiled down to the shortest path problem on \(G'\).

Since \(G'\) has \(N+M\) number of vertices, so it is still hopeless that it will finish in the time limit, but we can consider a graph \(G''\) in which edges of weight \(1\) are put together, as illustrated in the following diagram, so that the numbers of vertices and edges are reduced to \(\mathrm{O}(N)\).

Formally, the graph \(G''\) is defined as follows.

First, let

\(\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\).

Then,

• The vertices set of \(G''\) is \(\lbrace 1, 2, \ldots, N\rbrace \cup \mathcal{A}\).

• Also, for each \(i = 1, 2, \ldots, N\), there is a directed edge \(\overline{B_i} \rightarrow i\) of weight \(0\) a directed edge \(i \rightarrow \overline{(-A_i) \bmod M}\) of weight \(0\).

• Moreover, for each \(\overline{x} \in \mathcal{A}\), there is a directed edge \(\overline{x} \rightarrow \overline{y_x}\) of weight \((y-x) \mod M\). Here, \(\overline{y_x}\) is \(\overline{y} \in \mathcal{A} \setminus \lbrace \overline{x}\rbrace\) that minimizes \((y-x) \bmod M\).

We can use Dijkstra’s algorithm on this graph \(G''\) to solve this problem in a total of \(\mathrm{O}(N\log N)\) time.