CF2056A.Shape Perimeter

There is an $m$ by $m$ square stamp on an infinite piece of paper. Initially, the bottom-left corner of the square stamp is aligned with the bottom-left corner of the paper. You are given two integer sequences $x$ and $y$, each of length $n$. For each step $i$ from $1$ to $n$, the following happens:

• Move the stamp $x_i$ units to the right and $y_i$ units upwards.
• Press the stamp onto the paper, leaving an $m$ by $m$ colored square at its current position.

Note that the elements of sequences $x$ and $y$ have a special constraint: $1\le x_i, y_i\le m - 1$.

Note that you do not press the stamp at the bottom-left corner of the paper. Refer to the notes section for better understanding.

It can be proven that after all the operations, the colored shape on the paper formed by the stamp is a single connected region. Find the perimeter of this colored shape.

一张 $m$ 乘 $m$ 的正方形图章位于一张无限大的纸上。初始时，该正方形图章的左下角与纸张的左下角对齐。给定两个长度均为 $n$ 的整数序列 $x$ 和 $y$。对每个从 $1$ 到 $n$ 的步骤 $i$，执行以下操作：

• 将图章向右移动 $x_i$ 个单位，再向上移动 $y_i$ 个单位；
• 将图章按压在纸上，在其当前位置留下一个 $m$ 乘 $m$ 的着色正方形。

注意：序列 $x$ 和 $y$ 的元素满足特殊约束：$1\le x_i, y_i\le m - 1$。

注意：你不会在纸张左下角处按压图章。详见“说明”部分以获得更清晰的理解。

可以证明：在完成所有操作后，纸上由图章留下的着色图形是一个单连通区域。求该着色图形的周长。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 100$, $2 \le m \le 100$) — the number of operations performed and the side length of the square stamp.

The $i$-th of the next $n$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le m - 1$) — the distance that the stamp will be moved right and up during the $i$-th operation, respectively.

Note that there are no constraints on the sum of $n$ over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$2 \le m \le 100$）——分别表示执行的操作次数以及正方形图章的边长。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le m - 1$）——分别表示第 $i$ 次操作中图章向右和向上移动的距离。

注意：所有测试用例的 $n$ 值之和没有限制。

For each test case, output a single integer representing the perimeter of the colored shape on the paper.

对于每个测试用例，输出一个整数，表示纸上涂色图形的周长。

In the first example, the stamp has a side length of $3$ and is pressed $4$ times at coordinates $(1, 1)$, $(3, 3)$, $(5, 4)$, and $(6, 6)$. The piece of paper looks like that afterwards:

Here, the square formed by the first press is colored blue, the second red, the third green, and the fourth purple. The combined shape, whose perimeter we need to calculate, looks like that:

From the diagram, it can be seen that this shape has a perimeter of $32$.

在第一个示例中，印章的边长为 $3$，并在坐标 $(1, 1)$、$(3, 3)$、$(5, 4)$ 和 $(6, 6)$ 处各按压一次，共按压 $4$ 次。按压完成后，纸张如下所示：

其中，第一次按压形成的正方形涂为蓝色，第二次为红色，第三次为绿色，第四次为紫色。我们需要计算其并集形状的周长，该并集形状如下所示：

由图可知，该形状的周长为 $32$。