C. Тест на выносливость
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тест на выносливость FitnessGram — это многоступенчатый тест на аэробную способность, который постепенно становится сложнее по мере его прохождения. Тест на 20 метров начнется через 30 секунд. Встаньте на старт. Один круг должен быть завершен каждый раз, когда вы слышите этот звук. Динг! Не забудьте бежать по прямой и бегать как можно дольше. Тест начнется со слова "старт". На старт. Внимание!...

Фермер Джон проходит тест на выносливость FitnessGram! Фермер Джон тратит одну минуту, чтобы добежать до другой стороны зала. Поэтому в начале каждой минуты ФД может выбрать, либо пробежать до другой стороны зала, либо остаться на месте. Если он решает пробежать до другой стороны зала, он получает один балл.

ФД будет проходить тест на выносливость до начала $$$m$$$-й минуты. Изначально (в начале $$$0$$$-й минуты) ФД находится на стартовой стороне зала, которую мы будем обозначать как сторона $$$0$$$. Противоположная сторона зала обозначается как сторона $$$1$$$.

Аудиозапись теста на выносливость воспроизводится $$$n$$$ раз. В начале $$$a_i$$$-й минуты ФД должен находиться на $$$b_i$$$-й стороне зала.

Какое максимальное количество баллов ФД может набрать, выполняя требования аудиозаписи?

Входные данные

Первая строка содержит целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное количество баллов, которое ФД может набрать.

Пример
Входные данные
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$$$ ФД может остаться на стороне $$$0$$$.
  • В течение минуты $$$1$$$ ФД может пробежать на сторону $$$1$$$ и получить $$$1$$$ балл.
  • Непосредственно перед минутой $$$2$$$ аудиозапись требует, чтобы ФД находился на стороне $$$1$$$. Здесь ФД действительно находится на стороне $$$1$$$.
  • В течение минуты $$$2$$$ ФД может пробежать на сторону $$$0$$$ и получить $$$1$$$ балл.
  • В течение минуты $$$3$$$ ФД может остаться на стороне $$$0$$$.
  • Непосредственно перед минутой $$$4$$$ аудиозапись требует, чтобы ФД находился на стороне $$$0$$$. Здесь ФД действительно находится на стороне $$$0$$$.
  • Поскольку начало минуты $$$4$$$ наступило, тест на выносливость заканчивается. Его общий счет составляет $$$2$$$.

Соответствующая иллюстрация условия: