Let us formulate the problem as a minimum-cost flow problem.

Let us make a graph with \(N+1\) vertices numbered \(0\) to \(N\) and the following edges.

• Vertex \(j \to (j-1)\): capacity \(A_j\), cost \(-D\) (\(1 \leq j \leq N\))
• Vertex \(j \to (j-1)\): capacity \(M-A_j\), cost \(0\) (\(1 \leq j \leq N\))
• Vertex \((L_i-1) \to R_i\): capacity \(1\), cost \(C_i\) (\(1 \leq i \leq M\))

The cost of the minimum-cost circulation is the answer to the original problem multiplied by \(-1\), which can be seen from decomposing into cycles passing \((L_i-1) \to R_i\).

You can feed this graph to a strong library and solve the problem, but a minor modification can make it easier.

By preliminarily sending the maximum amount of flow up to the capacity along each edge \(j \to (j-1)\) (of both kinds), the minimum-cost circulation above can be reduced to the minimum-cost flow of capacity \(M\) from \(0\) to \(N\) in the following graph.

• Vertex \((j-1) \to j\): capacity \(A_j\), cost \(D\) (\(1 \leq j \leq N\))
• Vertex \((j-1) \to j\): capacity \(M-A_j\), cost \(0\) (\(1 \leq j \leq N\))
• Vertex \((L_i-1) \to R_i\): capacity \(1\), cost \(C_i\) (\(1 \leq i \leq M\))

We can solve this problem with the successive shortest path (primal-dual) algorithm. The complexity is \(O(N(N+M)\log(N+M))\).

Sample Submission (C++)