問題を最大フローで定式化すると，以下のようになります．

• グラフの頂点は，\(S\),\(T\),\(L_1,L_2,\cdots,L_N\),\(R_1,R_2,\cdots,R_M\) であるとする．

• 各 \(1 \leq i \leq N\) について，\(S \rightarrow L_i\) に容量 \(A_i\) の辺を張る．

• 各 \(1 \leq i \leq N\), \(1 \leq j \leq M\) について，\(L_i \rightarrow R_j\) に容量 \(B_j\) の辺を張る．

• 各 \(1 \leq j \leq M\) について，\(R_j \rightarrow T\) に容量 \(C_j\) の辺を張る．

• \(S \rightarrow T\) の最大フローが答えになる．

もちろん，このグラフは大きすぎるため直接フローは計算できません． そこで，最大フローが最小カットに一致することを用いて，最小カットを求めることを考えます．

頂点 \(L_i\) の中で，\(S\) 側のカットに含まれる集合を \(X\)，それ以外の集合を \(Y\) と決定したとします．

すると，各頂点 \(R_j\) について，それがカットのどちら側に含まれるかは，\(R_j\) ごとに独立に決定できます． つまり，\(S\) 側に含まれた場合のコスト\(=C_j\) と，\(T\) 側に含まれた場合のコスト \(=|X|B_j\) を比較し，その小さい方に割り振れば良いです．

ここで，\(X,Y\) を決めたあとに重要なのは \(X\) のサイズだけでした． なので，\(X\) のサイズを決定したあと，\(L_i\) については \(A_i\) の値の大きい方から \(X\) として使えばよいです．

\(X\) のサイズを \(0\) から \(N\) まですべて試し，それぞれでカットの値を求めます． \(A_i\) のソート以外は，累積和を使うことで，\(O(N+M)\) 時間で行なえます． よって，計算量は全体で \(O(N \log N + M)\) です．