Dungeon Raid

At level $X$, only dungeons satisfying $A_i < X$ need to be considered. Challenging any other dungeon does not increase the level, so doing so cannot be better than postponing it.

Among the currently available dungeons, choose one with the smallest $B_i$. If its second difficulty value is $B$, the new level is

$$X+\min(X,B).$$

For two currently available dungeons with second difficulty values $b \leq c$, challenging them in the order $b,c$ leaves the level at least as large as challenging them in the order $c,b$. Repeating this exchange argument shows that choosing the smallest available $B_i$ first does not lose an optimal solution.

Sort the dungeons by $A_i$. Insert every $B_i$ whose dungeon satisfies $A_i < X$ into a min-heap, remove the smallest value, and update the level. If the heap is empty, none of the remaining dungeons can increase the level, so the process ends.

The time complexity is $O(N\log N)$ and the space complexity is $O(N)$. The final level is at most $L+\sum B_i \leq 5.00001\times 10^{17}$, which fits in a signed 64-bit integer.

Solution written by GPT5