← 返回题目列表

Codeforces · 2148/C

C. 步行者

中文机器翻译题面 查看原题

FitnessGram 起搏器测试是一项多阶段有氧能力测试,随着测试的进行,难度会逐渐增加。 20米配速测试将在30秒后开始。一开始就排队。每次听到此声音时,就应该完成一圈。叮!记住要沿直线跑,并且跑得尽可能远。测试将从单词 start 开始。就你的目标而言。准备好!...

Farmer John 正在运行 FitnessGram 起搏器测试!农夫约翰采取 一分钟 跑到健身房的另一边。因此,在每一分钟开始时,FJ可以选择要么跑到健身房的另一边,要么留在原地。如果他选择跑到体育馆的另一边,他就会获得 一点.

FJ 将运行起搏器测试,直到第 $$$m$$$ 分钟开始。最初(在第 $$$0$$$ 分钟开始时),FJ 位于健身房的起始侧,我们将其表示为 $$$0$$$ 侧。健身房的另一侧表示为 $$$1$$$ 侧。

起搏器测试音频播放 $$$n$$$ 次。在第 $$$a_i$$$ 分钟开始时,FJ 必须位于健身房的第 $$$b_i$$$ 侧。

在确保满足音频要求的情况下,FJ 最多可以获得多少分?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5, n \leq m \leq 10^9$$$) - 需求数量和总分钟数。

以下 $$$n$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ $$$(1 \leq a_i \leq m, b_i \in \{0,1\})$$$ - 音频的第 $$$i$$$ 要求。保证 $$$a_i \gt a_{i-1}$$$ 超过所有 $$$i \gt 1$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出FJ可以获得的最大点数。

示例

输入
复制

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$$$分钟内,FJ可以留在$$$0$$$一边。
  • 在$$$1$$$分钟内,FJ可以跑到$$$1$$$一边并获得$$$1$$$点。
  • 就在 $$$2$$$ 分钟之前,音频要求 FJ 在 $$$1$$$ 旁边。在这里,FJ 确实站在 $$$1$$$ 一边。
  • 在$$$2$$$分钟内,FJ可以跑到$$$0$$$一边并获得$$$1$$$点。
  • 在$$$3$$$分钟内,FJ可以留在$$$0$$$一边。
  • 就在 $$$4$$$ 分钟之前,音频要求 FJ 在 $$$0$$$ 旁边。在这里,FJ确实站在$$$0$$$一边。
  • 由于已达到 $$$4$$$ 分钟的开始时间,起搏器测试结束。他的总分是$$$2$$$。

声明相关说明: