Formularizing the problem with maximum flow, we get the following.

• The graph has the vertices \(S\),\(T\),\(L_1,L_2,\cdots,L_N\),\(R_1,R_2,\cdots,R_M\).

• For each \(1 \leq i \leq N\), there is an edge \(S \rightarrow L_i\) with a capacity \(A_i\).

• For each \(1 \leq i \leq N\) and \(1 \leq j \leq M\), there is an edge \(L_i \rightarrow R_j\) with a capacity \(B_j\).

• For each \(1 \leq j \leq M\), there is an edge \(R_j \rightarrow T\) with a capacity \(C_j\).

• The answer is the maximum flow from \(S\) to \(T\).

Naturally, the graph is too large to compute the flow directly. Let us try to find the minimum cut instead, which is equal to the maximum flow.

Assume that we have split the vertices \(L_i\) to the sets \(X\) and \(Y\) ― the former sides with \(S\) in the cut, and the latter sides with \(T\).

Then, for each vertex \(R_j\), we can independently decide whether it sides with \(S\) or \(T\) in the cut. That is, we compare the cost when \(R_j\) belongs to \(S\), which is \(C_j\), and the cost when \(R_j\) belongs to \(T\), which is \(|X|B_j\), and choose the side with the smaller cost.

Here, after choosing \(X\) and \(Y\), it was just the size of \(X\) that mattered. Therefore, we can first decide the size of \(X\), and then choose the vertices to be used as \(X\) from \(L_i\) in descending order of \(A_i\).

We will try all possible sizes of \(X\) from \(0\) to \(N\) and find the costs of the corresponding cuts. Except for sorting \(A_i\), this can be done in \(O(N+M)\) time with prefix sums. Thus, the total time complexity of this solution is \(O(N \log N + M)\).