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可以获得的最大点数。
示例
输入复制
32 42 14 02 71 14 04 91 02 06 19 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$$$。
声明相关说明: