好的，我们先明确题意，然后结合题目例子和常见解法思路给出详细题解。

---

题目理解

FJ 在时刻 $0$ 位于 侧面 $0$。
一共有 $m$ 分钟（时间从 $1$ 到 $m$，但注意“第 $i$ 分钟开始时”的状态会受前一分钟决策影响）。
每分钟开始时，FJ 可以：

• 留在当前侧面（不得分）
• 或者 换到对面（并立即获得 $1$ 分）

此外，有 $n$ 个硬性要求： 在第 $a_i$ 分钟开始时，FJ 必须 在侧面 $b_i$。

问：在满足所有音频要求的前提下，FJ 最多能获得多少分（即最多“换边”多少次）？

---

关键约束

• $a_i$ 严格递增，$1 \le a_i \le m$。
• 初始时（$t=0$）在侧面 $0$，且要求只在 $t \ge 1$ 时给出。
• 如果 $t$ 时刻没有要求，FJ 可以自由选择留在原位或换边（换边即得分+1）。
• 如果有要求，$t$ 时刻位置必须等于 $b_i$。

---

模型转化

设：

• $p_t \in \{0,1\}$ 表示第 $t$ 分钟开始时（即从 $t-1$ 分钟结束到 $t$ 分钟开始之间决策后）的位置。
• 初始 $p_0 = 0$。
• 第 $t$ 分钟开始时的决策：可以选择 $p_{t} = p_{t-1}$（不换边，不得分） 或 $p_{t} = 1 - p_{t-1}$（换边，得分+1）。

要求：$p_{a_i} = b_i$。

目标：最大化 换边次数。

等价地，我们要求 最少的“停留”次数 来满足位置约束，因为 $m$ 分钟内最多可能换 $m$ 次（每分钟都换），但约束会强制某些时刻不能换或必须换。

---

区间思维

把 $a_i$ 看作强制点。

考虑相邻两个强制点 $(a_i, b_i)$ 和 $(a_{i+1}, b_{i+1})$，中间 $[a_i, a_{i+1}]$ 这段（注意是时间点，不是时刻间隔）。

我们关心：从 $p_{a_i} = b_i$ 出发，经过 $a_{i+1} - a_i$ 次分钟（每次可换或不换），到达 $p_{a_{i+1}} = b_{i+1}$，最多能换几次？

---

换边次数限制

设 $d = a_{i+1} - a_i$。

结论：

• 如果 $b_i = b_{i+1}$，即两端相同，那么：

  • 最少换边次数（最少得分为）$d \% 2$（因为每两次换边回到原位，要满足同侧，必须换偶数次）。
  • 最多换边次数为 $d$（如果允许，但必须满足奇偶性约束）。
  • 实际可达的换边次数与 $d$ 同奇偶，且介于 $0$ 和 $d$ 之间。

• 如果 $b_i \ne b_{i+1}$，即两端不同：

  • 最少换边次数为 $1$（换奇数次，最小是 $1$），
  • 最多换边次数还是 $d$，且必须奇数次。

更精确：
可达的换边次数集合是：

$$\{ k \mid k \equiv (b_i \neq b_{i+1}) \pmod{2},\ 0 \le k \le d \} $$

但 $k=0$ 只在相同且 $d$ 偶时才可能；$k=1$ 只在不同且 $d\ge 1$ 时才可能。

不过我们要 最大化总分，所以我们要尽量选大的 $k$，但需要保证全局可行。

---

抽象成区间问题

设 $x_i$ 表示第 $i$ 个强制点后的“累积换边次数”奇偶性相关变量。

实际上，我们可以用 距离 = 时间差 mod 2 来推导约束。

令 $f_i$ 表示从起点到第 $i$ 个强制点（包含）的总换边次数。

那么：

$$p_{a_i} = (p_0 + f_i) \bmod 2 = (0 + f_i) \bmod 2$$

因为每次换边会翻转位置，$f_i$ 就是到此时为止的换边次数。

要求 $p_{a_i} = b_i$，所以：

$$f_i \equiv b_i \pmod{2}$$

同时，从 $a_i$ 到 $a_{i+1}$：

$$f_{i+1} - f_i = \text{换边次数在区间内}$$

设 $k_i = f_{i+1} - f_i$，则：

• $0 \le k_i \le d_i$，其中 $d_i = a_{i+1} - a_i$。
• 奇偶性：$k_i \equiv b_{i+1} - b_i \pmod{2}$（模 2）。

并且 $f_1$ 对应第一个强制点：$f_1 \equiv b_1$。

---

贪心/DP 构造

已知 $f_0 = 0$，但强制点从 $a_1$ 开始。
从 $t=0$ 到 $a_1$，有 $a_1$ 分钟，我们可以任意安排换边次数 $f_1$（与 $b_1$ 同奇偶），且 $0 \le f_1 \le a_1$。

然后对于 $i=1$ 到 $n-1$，$k_i = f_{i+1} - f_i$，有：

• $k_i \equiv b_{i+1} - b_i \pmod{2}$
• $0 \le k_i \le d_i$

从 $f_i$ 可推 $f_{i+1} = f_i + k_i$，必须满足 $0 \le f_{i+1} \le a_{i+1}$（因为最多每分钟换一次，所以总换边次数不能超过时间）。

最后，最后一个强制点后，从 $a_n$ 到 $m$，还有 $m - a_n$ 分钟，可以继续换边，最大可加分 $\min(m - a_n,\ \text{剩余时间})$ 且奇偶性要匹配最后位置，但注意这最后一段时间没有强制要求，所以可以最大化到 $\min(m - a_n,\ \text{时间差})$ 且不必考虑奇偶（因为可以最后一步不换）。

但准确说：最后一段若 $a_n$ 到 $m$ 有 $T = m - a_n$ 分钟，我们可以选择在每分钟是否换边，没有奇偶约束（因为结束时没有要求），所以最多可以换 $T$ 次，即最后一段的最大得分就是 $T$。

---

简化做法

其实这个问题可以简化为：

1. 要求 $f_i \equiv b_i$，且 $0 \le f_i \le a_i$（因为不能超过时间）。
2. $f_{i+1} - f_i$ 与 $b_{i+1} - b_i$ 同奇偶，并且 $\le d_i$。
3. 要最大化 $f_n + (m - a_n)$（最后一段全换）。

所以关键是最大化 $f_n$，同时满足递推。

---

递推求最大 $f_n$

设 $F_i$ 表示第 $i$ 个强制点时刻 $a_i$ 时能达到的最大 $f_i$。

初始 $F_1 = \max \{ x \mid x \equiv b_1, 0 \le x \le a_1 \}$
即 $F_1 = a_1$ 如果 $a_1 \equiv b_1$，否则 $a_1 - 1$。

递推：
$F_{i+1} = \min(a_{i+1},\ F_i + d_i)$ 且奇偶性必须 $F_{i+1} \equiv b_{i+1}$。

所以 $F_{i+1} = \min(a_{i+1},\ F_i + d_i)$ 再调整到满足奇偶性（减 0 或 1）。

---

检查可行性

同时要检查下界：
最小可达 $f_{i+1}$ 为 $L_{i+1} = \max(0,\ F_i - d_i)$ 吗？等等，不对，因为我们考虑的是 $k_i \ge 0$，所以 $f_{i+1} \ge f_i - d_i$ 不对，因为 $k_i = f_{i+1} - f_i$ 可正可负？
不能负，因为 $k_i \ge 0$，即 $f_{i+1} \ge f_i$。

所以 $f_i$ 必须非递减。
因此 $f_{i+1} \ge f_i$。

这很重要：换边次数 不会减少，因为每个 $k_i$ 是区间内增加的次数。

所以 $f_i$ 序列单调不减。

---

正确递推

我们有：

• $f_{i+1} \ge f_i$
• $f_{i+1} \equiv b_{i+1}$
• $f_{i+1} \le a_{i+1}$
• $f_{i+1} \le f_i + d_i$

并且 $f_{i+1} - f_i \equiv b_{i+1} - b_i$。

因此，从 $f_i$ 出发，要选一个 $\ge f_i$ 且同余 $b_{i+1}$ 的最大值不超过 $\min(a_{i+1},\ f_i + d_i)$。

设 $M = \min(a_{i+1},\ f_i + d_i)$。

$M$ 可能不满足同余，需要减少到满足同余的最接近值。

所以：

$$f_{i+1} = M - ((M - b_{i+1}) \bmod 2)$$

同时要检查 $f_{i+1} \ge f_i$，如果 $f_{i+1} < f_i$，说明不可能，输出 $-1$（但题目保证一定有解？不一定，题目没说无解情况，可能输入保证有解，但我们仍可以判断）。

---

初始和最终答案

$f_1$ 同样由 $\min(a_1,\ a_1)$ 且同余 $b_1$ 得： $f_1 = a_1$ 若 $a_1 \equiv b_1$，否则 $a_1 - 1$，但要检查 $f_1 \ge 0$。

最终答案 = $f_n + (m - a_n)$。

---

算法步骤

1. 读 $n, m$ 和要求数组 $(a_i, b_i)$。
2. 对第一个要求：
   • $f = a_1$，若 $f \% 2 \ne b_1$ 则 $f = a_1 - 1$。
   • 如果 $f < 0$，则无解（实际不会）。
3. 对 $i$ 从 1 到 $n-1$：
   • $d = a_{i+1} - a_i$
   • $M = \min(a_{i+1},\ f + d)$
   • $f_{next} = M - ((M - b_{i+1}) \& 1)$
   • 如果 $f_{next} < f$ 或 $f_{next} > a_{i+1}$ 或 $f_{next} < 0$，则无解（实际输入保证有解）
   • $f = f_{next}$
4. 答案 = $f + (m - a_n)$
5. 输出答案

---

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    
    ll f;
    // 处理第一个要求
    if (a[0] % 2 == b[0]) {
        f = a[0];
    } else {
        f = a[0] - 1;
    }
    if (f < 0) f = -1; // 无解标记
    
    for (int i = 0; i < n - 1; ++i) {
        if (f < 0) break;
        ll d = a[i+1] - a[i];
        ll M = min(a[i+1], f + d);
        ll nxt = M - ((M - b[i+1]) & 1);
        if (nxt < f || nxt < 0) {
            f = -1;
            break;
        }
        f = nxt;
    }
    
    if (f < 0) {
        // 按照题目保证，这里不会执行
        cout << -1 << "\n";
    } else {
        cout << f + (m - a[n-1]) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

复杂度

每个测试用例 $O(n)$，总 $n$ 和 $\le 2\times 10^5$，轻松通过。