Codeforces Round 1050 (Div. 4)

C. 节奏跑 (Pacer)

每个测试的时间限制： 2 秒 内存限制： 256 兆字节

题目描述

“FitnessGram 节奏跑测试（Pacer Test）”是一种多阶段的有氧能力测试，随着测试的进行会逐渐变难。20 米节奏跑测试将在 30 秒后开始。排好队站在起点。每当你听到提示音“叮！”，就应当完成一次往返。记住要沿直线奔跑，并尽可能坚持下去。测试将在口令“开始”时启动。各就位，预备……

农夫 John 正在进行节奏跑测试！John 花费 1 分钟可以从体育馆的一边跑到另一边。 因此，在​每一分钟开始时​，他可以选择：

• 跑到体育馆的另一边（此时他获得 1 分）；
• 或者留在原地（得分不变）。

节奏跑会持续到第 m 分钟开始为止。 最初（在第 0 分钟开始时），John 位于体育馆的​0 号边​；体育馆的另一侧记作​1 号边​。

节奏跑的音频会播放 n 次提示。 在第 aᵢ 分钟开始时，John 必须位于体育馆的 bᵢ 号边。

问题： 在满足所有音频要求的前提下，John 最多可以获得多少分？

输入格式

• 第一行包含一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例的数量。
• 每个测试用例：
  • 第一行包含两个整数 n, m (1 ≤ n ≤ 2×10⁵, n ≤ m ≤ 10⁹)，分别表示要求的条数和总分钟数。
  • 接下来 ​n 行​，每行包含两个整数 aᵢ, bᵢ (1 ≤ aᵢ ≤ m, bᵢ ∈ {0,1})，表示在第 aᵢ 分钟开始时，John 必须位于 bᵢ 号边。
  • 保证 aᵢ 严格递增：aᵢ > aᵢ₋₁。
• 保证所有测试用例中 n 的总和不超过 2×10⁵。

输出格式

对于每个测试用例，输出一个整数，表示 John 在满足要求的情况下最多能获得的分数。

示例输入

3
2 4
2 1
4 0
2 7
1 1
4 0
4 9
1 0
2 0
6 1
9 0

示例输出

2
7
6

说明

对于第一个样例测试：

• 第 0 分钟：John 停留在边 0。
• 第 1 分钟：John 跑到边 1，获得 1 分。
• 在第 2 分钟开始前：音频要求 John 在边 1，满足要求。
• 第 2 分钟：John 跑到边 0，获得 1 分。
• 第 3 分钟：John 停留在边 0。
• 在第 4 分钟开始前：音频要求 John 在边 0，满足要求。
• 到达第 4 分钟开始时，测试结束。总得分为 2。

（题目原文给出了相应的示意图。）