A. Периметр фигуры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечном листе бумаги находится квадратная печать размером $$$m$$$ на $$$m$$$. Изначально левый нижний угол квадратной печати выравнивается по левому нижнему углу листа. Вам даны две целочисленные последовательности $$$x$$$ и $$$y$$$, каждая длиной $$$n$$$. Для каждого шага $$$i$$$ от $$$1$$$ до $$$n$$$ происходит следующее:

  • Переместите печать на $$$x_i$$$ единиц вправо, а затем на $$$y_i$$$ единиц вверх.
  • Прижмите печать к бумаге, оставив цветной квадрат размером $$$m$$$ на $$$m$$$ на месте печати.

Обратите внимание, что элементы последовательностей $$$x$$$ и $$$y$$$ имеют дополнительное ограничение: $$$1\le x_i, y_i\le m - 1$$$.

Обратите внимание, что вы не ставите печать в левом нижнем углу листа. Обратитесь к примечаниям для лучшего понимания.

Можно доказать, что после всех операций цветная фигура на бумаге, сформированная печатями, представляет собой единую связанную область. Найдите периметр этой цветной фигуры.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100$$$, $$$2 \le m \le 100$$$) — количество выполненных операций и длину стороны квадратной печати.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le m - 1$$$) — расстояние, на которое печать будет перемещена вправо и вверх во время $$$i$$$-й операции соответственно.

Обратите внимание, что нет дополнительного ограничения на сумму $$$n$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите одно целое число — периметр цветной фигуры на бумаге.

Пример
Входные данные
3
4 3
1 1
2 2
2 1
1 2
1 2
1 1
6 7
3 6
1 1
3 1
6 6
5 4
6 1
Выходные данные
32
8
96
Примечание

В первом наборе входных данных печать имеет длину стороны $$$3$$$ и нажимается $$$4$$$ раза на координатах $$$(1, 1)$$$, $$$(3, 3)$$$, $$$(5, 4)$$$ и $$$(6, 6)$$$. После этого лист бумаги выглядит так:

Здесь квадрат, образованный первым нажатием, окрашен в синий цвет, вторым — в красный, третьим — в зеленый, а четвертым — в фиолетовый. Объединённая фигура, периметр которой нам нужно вычислить, выглядит следующим образом:

Периметр этой фигуры равен $$$32$$$.