\(a_i \leq N-1\) としてよいです。 これはランプのコストは最大でも \(N-1\) しか下がらないためです。
\(N \le a_i \) の場合は \(X\) から \(a_i -(N-1)\) を差し引くことで \(a_ i \le N-1\) を満たすようにすることができます。
ここから \(X \leq N(N-1)\) と考えてよいことがわかります。
また、「コストが \(1\) 以上のランプのコストが全て \(1\) 小さくなる」というのは「 \(i\) 個目のランプを灯したあと、 まだ灯されていないランプのうち、コストが \(i\) 以上のランプの個数だけ最終的なMPの消費量が小さくなる」と言い換えられます。

これらを利用して、灯ったランプの個数、残っているコストが \(i\) 以下のランプの個数、現在の MP をキーに DP することで答えを求めることができます。
これは \(O(N^4)\) で実行可能で十分高速です。