Pacer

We need maximize points, and a point is gained exactly when FJ runs across the gym during a minute. Running flips his side. Staying keeps his side.

So the entire problem is secretly about parity. Classic Codeforces disguise: goofy story, tiny math core. The pacer test lore is just seasoning.

Key Observation

Suppose FJ is at side $s$ at time $t$, and later he must be at side $b$ at time $a$.

There are

$$d = a - t$$

minutes available in this interval.

If he runs $r$ times during those $d$ minutes, then his side changes iff $r$ is odd. Therefore:

$$r \bmod 2 = s \oplus b$$

where $s \oplus b$ is $0$ if the sides are the same and $1$ if they are different.

Also, since each run gives one point, we want $r$ as large as possible.

Best Score Inside One Interval

The maximum possible number of runs is obviously $d$, because there are only $d$ minutes.

Now check whether running every minute lands on the required side:

• If $d \bmod 2 = s \oplus b$, then running all $d$ minutes works, so we gain $d$ points.
• Otherwise, running all $d$ minutes lands on the wrong side. Skip exactly one run, gain $d-1$ points, and now the parity is fixed.

That is the whole trick. You never need to skip two runs, because skipping one changes parity and loses the minimum possible score.

So for each constrained interval:

$$\text{gain} = d - [d \bmod 2 \ne s \oplus b]$$

where the bracket is $1$ if true, otherwise $0$.

Handling All Requirements

The requirements are already sorted by time. We start at:

$$\text{prevTime}=0, \quad \text{prevSide}=0$$

For each requirement $(a_i,b_i)$:

1. Let $d = a_i - \text{prevTime}$.
2. Compute the needed parity: $\text{prevSide} \oplus b_i$.
3. Add $d$ if the parity matches, otherwise add $d-1$.
4. Update prevTime = a_i, prevSide = b_i.

After the final requirement, there are no more side constraints. At that point, FJ should just run every remaining minute like his GPA depends on it:

$$m - \text{prevTime}$$

Add that directly.

Why Greedy Works

Each interval is independent once you know its start side and end side. The requirements force the boundary sides, so choices inside one interval do not affect any later interval except through the already-fixed endpoint. Therefore, maximizing each interval separately gives the global maximum.

No dynamic programming needed. No graph. No simulation minute-by-minute, because $m$ can be up to $10^9$. Just parity and vibes.

Complexity

For each test case, we process the $n$ requirements once.

$$O(n)$$

Total over all test cases is $O(\sum n)$, which fits easily.