We may assume \(a_i \leq N-1\). This is because the cost of a lamp decreases by at most \(N-1\).
If \(N \le a_i\), we can subtract \(a_i -(N-1)\) from \(X\) to ensure \(a_i \le N-1\).
From this, we can assume \(X \leq N(N-1)\).
Also, “the cost of all lamps with cost at least \(1\) decreases by \(1\)” can be rephrased as “after lighting the \(i\)-th lamp, the final MP consumption decreases by the number of unlit lamps with cost at least \(i\).”

Using these observations, we can find the answer by performing DP with keys being the number of lit lamps, the number of remaining lamps with cost at most \(i\), and the current MP.
This can be executed in \(O(N^4)\), which is sufficiently fast.