\(N+4\) 頂点 \(2(N+M)\) 辺 の最小費用流で解けます。

\(N+1 \rightarrow s_{i} : (\text{cap} \;1,\text{cost}\;0)\;(1\leq i\leq M)\)
\(e_{i} \rightarrow N+2 : (\text{cap} \;1,\text{cost}\;0)\;(1\leq i\leq M)\)
\(i \rightarrow N+3 : (\text{cap} \;1,\text{cost}\;X_{i})\;(1\leq i\leq N)\)
\(N+2 \rightarrow N+3 : (\text{cap} \;M-K,\text{cost}\;0)\)
\(i\rightarrow i+1:(\text{cap}\; A_{i},\text{cost}\;0)\;(1\leq i\lt N)\)

ただし、\(A_{i}\) は、\(s_{j}\leq i\lt e_{j}\) を満たす \(j\) の数とします。

イメージとしては、宿題が頂点 \(N+1\) から流れてきて、できたら \(N+3\) に流し、締め切りの日になったら \(N+2\) に流すというイメージです。

\(i\rightarrow i+1\) は翌日に宿題を持ち込むイメージで、ここの流量を \(A_{i}\) で制限することで締め切り後に提出することを防いでいます。

実装例(c++ 37ms)