Construct the following directed graph \(G'\) with \(2N\) vertices and \(2M + N - 2\) edges:

• The set of vertices consist of \(1, 2, \dots, N\) and \(1', 2', \dots, N'\).
• For each \(2 \leq i \leq N-1\), add an edge \(i \to i'\) with capacity \(c_i\).
• For each \(1 \leq j \leq M\), add edges \(a_i' \to b_i\) and \(b'_i \to a_i\) with capacity \(\inf\).

Then, actually the following fact follows.

The cost \(C\) of building walls to satisfy the condition is equal to the capacity of minimum cut on \(G'\) with source \(1'\) and sink \(N\).

We will check that step-by-step.

Observation 1

Let \(G\) be the undirected graph given in the original problem. There is a bijection between vertex-disjoint paths on \(G\) between \(1 - N\) and vertex-disjoint paths on \(G'\) between \(1' - N\). (A path is said to be vertex-disjoint if no vertex appears twice or more.)

Take a closer look at \(G'\). For each \(a\), the only edge going out from \(a\) is \(a'\), and all the edges going out from \(a'\) end at vertices without primes. Therefore, a path on \(G'\) between \(1' - N\) can be expressed as \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\). Then, we can see that

• a vertex-disjoint path \(1=p_0,p_1,\dots,p_k=N\) on \(G\) and
• a vertex-disjoint path \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\) on \(G'\)

correspond one-by-one, because one can be uniquely determined by another.

Observation 2

Let \(S \subseteq \lbrace 2,3,\dots,N-1 \rbrace\), then the following two propositions are equivalent.

1. When walls are built on vertices \(S\), then Aoki cannot travel from Vertex \(1\) to Vertex \(N\).
2. When edges from \(i\) to \(i'\) are removed for all \(i \in S\), then there will be no path \(1' \to N\).

Proposition 1 can be reworded as follows: for all vertex-disjoint path \(p_0,p_1,\dots,p_{k-1},p_k\) between \(1 - N\) on \(G\), there exists \(v \in S\) such that \(v \in \lbrace p_1,\dots,p_{k-1}\rbrace\).
In such case, the corresponding path \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\) on \(G'\) defined in Observation 1 contains Edge \(v \to v'\), so removing \(v \to v'\) invalidates this path. We omit the details, but this sort of discussion justifies the claim.

By the observations above, the original problem is boiled down to a minimum-cut problem on \(G'\) where only edges \(v \to v'\) \((2 \leq v \leq N-1)\) are allowed to be cut.

By using AtCoder Library, it can be computed in a total of \(\mathrm{O}(N^2M)\) time including the construction of the minimum cut, so the problem can be solved fast enough.