The optimal strategy

We may only consider the following strategy without changing the answer:

At most one stage is cleared multipole times. If any, then it is the last stage among the stages to be cleared.

This can be proved as follows.

Let \(1, \dots, M\) be the stages that were cleared at least once. Let \(m\) be one of \(i = 1, \dots, M\) with the smallest \(B_i\). Then, we may assume that only Stage \(m\) is cleared twice or more. This is because, if any other Stage \(i\) is cleared twice or more, we may replace it with Stage \(i\) without increasing the cost, since \(B_i \geq B_m\).

Moreover, if \(m \lt M\), then for \(i\) such that \(m \lt i \leq M\) it holds that \(A_i + B_i \gt B_i \geq B_m\), so the time required to clear Stage \(i\) for the first time is greater than that of clearing Stage \(m\) for the second time and later. As we already shown that Stage \(i\) is cleared exactly once, we may replace the first clears of Stages \(m + 1, \dots, M\) with those of Stage \(m\) without increasing the cost.

Calculating the answer

We could narrow down the optimal strategy to very simple ones. Thus, it is sufficient that we exhaustively search over \(M\) to try “clear Stage \(1\) through \(<\) once and spend all remaining quota on clearing Stage \(M\) for the second time and later,” and find the minimum value.

We need to find “the time required to clear Stage \(1\) through Stage \(M\) once each.” By increasing \(M\) one by one, it can be updated only by repeatedly “adding \(A_i+B_i\) to the current value.” Therefore, the problem has been solved in a total of \(O(N)\) time.

Note that you need to rule out \(M\) such that \(M \gt X\).

実装例 (C++)