問題を最小費用流で定式化します．

\(0\) から \(N\) までの番号のついた \(N+1\) 頂点のグラフを用意し，以下のように辺を張ります．

• 頂点 \(j \to (j-1)\)，容量 \(A_j\)，コスト \(-D\) (\(1 \leq j \leq N\))
• 頂点 \(j \to (j-1)\)，容量 \(M-A_j\)，コスト \(0\) (\(1 \leq j \leq N\))
• 頂点 \((L_i-1) \to R_i\)，容量 \(1\)，コスト \(C_i\) (\(1 \leq i \leq M\))

このグラフの最小費用循環流のコストは，元の問題の答えを \(-1\) 倍したものになっています． これは，\((L_i-1) \to R_i\) を通るサイクルごとに分解して考えるとわかります．

強力なライブラリがあればこのグラフをそのまま与えて問題を解くこともできますが，すこし変形すると問題はより簡単になります．

頂点 \(j \to (j-1)\) の辺（\(2\) 種類とも）に予め容量最大までフローを流すことにすると，上の最小費用循環流は，以下のグラフ上の \(0 \to N\) の容量 \(M\) の最小費用流に帰着されます．

• 頂点 \((j-1) \to j\)，容量 \(A_j\)，コスト \(D\) (\(1 \leq j \leq N\))
• 頂点 \((j-1) \to j\)，容量 \(M-A_j\)，コスト \(0\) (\(1 \leq j \leq N\))
• 頂点 \((L_i-1) \to R_i\)，容量 \(1\)，コスト \(C_i\) (\(1 \leq i \leq M\))

この問題は，最短路反復法（primal-dual）で解くことができます． 計算量は \(O(N(N+M)\log(N+M))\) になります．

解答例(c++)