This Is the Last Time

The annoying-looking part of this problem is the interval condition:

You can play casino $i$ only when

$l_i \le x \le r_i$

and then your coins become $real_i$.

At first this looks like a graph/reachability problem where you may need to jump up, jump down, carefully choose order, maybe sacrifice coins to unlock something later. That is the false assumption. Decreasing your coin count is basically a trap here.

The key observation

Suppose your current number of coins is $x$.

A casino is useful only if it can increase your coins, meaning:

$real_i > x$

If also $l_i \le x$, then this casino is definitely playable.

Why? Because the statement guarantees:

$l_i \le real_i \le r_i$

Since $real_i > x$, we get:

$r_i \ge real_i > x$

So $x \le r_i$ automatically.

That means for an improving move, the upper bound $r_i$ does not matter at all. If $l_i \le x$ and $real_i > x$, you can play it. Done.

If $real_i \le x$, then the casino cannot improve your maximum answer anyway. Maybe it is playable, maybe it is not, who cares. It cannot directly give you more coins, and lowering your coins never helps unlock a better final value: any casino with a higher $real$ would have a high enough $r$ to also accept the larger coin count once its $l$ is satisfied.

So what remains?

Each casino is basically:

• requirement: need at least $l_i$ coins
• reward: after playing, you may have $real_i$ coins

We start with $ans = k$.

If some casino has $l_i \le ans$, then it is worth considering. It can raise our answer to:

$ans = \max(ans, real_i)$

After $ans$ increases, more casinos may become available, because their $l_i$ requirement might now be satisfied.

This screams sorting.

Algorithm

Sort all casinos by $l_i$.

Then scan from left to right:

1. Start with $ans = k$.
2. While the next casino has $l_i \le ans$, process it.
3. Processing means $ans = \max(ans, real_i)$.
4. If the next casino has $l_i > ans$, stop.

Why can we stop? Because the casinos are sorted by $l_i$. If the smallest remaining $l_i$ is too large, then every other remaining casino also has $l_i > ans$. You cannot reach any of them.

Correctness proof

Let $ans$ be the value maintained by the algorithm.

First, every increase the algorithm makes is legal. When it processes a casino with $l_i \le ans$:

• if $real_i \le ans$, nothing changes;
• if $real_i > ans$, then $r_i \ge real_i > ans$, so the current $ans$ satisfies $l_i \le ans \le r_i$ and the casino can be played.

So the algorithm never invents fake coins. Every new value of $ans$ is reachable.

Now we show the algorithm cannot miss a better answer.

When the algorithm stops, the next unprocessed casino has $l_i > ans$. Since the list is sorted, every unprocessed casino also has $l_i > ans$.

To get more than $ans$, some remaining casino would need to be played eventually and increase the coin count. But before playing it, you would need at least $l_i$ coins, and $l_i > ans$. The algorithm has already found the maximum reachable coin count among everything with $l_i \le ans$, so there is no way to cross that gap.

Therefore no unprocessed casino can help, and $ans$ is the maximum final number of coins.

Complexity

Sorting dominates:

$O(n \log n)$

per test case, with total $n \le 10^5$, so this easily fits. Memory is $O(n)$.

Tiny punchline: $r_i$ is not useless in the statement, but for the maximizing logic it gets completely bodied by $real_i \le r_i$.