← 返回题目列表

Codeforces · 2056/A

A. 形状周长

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

在一张无限大的纸上有一个 $$$m$$$ by $$$m$$$ 的方形邮票。最初,方形图章的左下角与纸张的左下角对齐。给定两个整数序列 $$$x$$$ 和 $$$y$$$,每个长度为 $$$n$$$。对于从 $$$1$$$ 到 $$$n$$$ 的每个步骤 $$$i$$$,会发生以下情况:

- 将标记向右移动 $$$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$$$) - 执行的操作数量和方形印章的边长。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le m - 1$$$) - 分别是在第 $$$i$$$ 操作期间图章将向右和向上移动的距离。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出一个整数,表示纸上彩色形状的周长。

示例

输入 #1

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

输出 #1

32
8
96

注意

在第一个示例中,图章的边长为 $$$3$$$,并在坐标 $$$(1, 1)$$$、$$$(3, 3)$$$、$$$(5, 4)$$$ 和 $$$(6, 6)$$$ 处按下 $$$4$$$ 次。之后这张纸看起来像这样:

此处,第一次按形成的正方形颜色为蓝色,第二次为红色,第三次为绿色,第四次为紫色。我们需要计算其周长的组合形状如下所示:

从图中可以看出,这个形状的周长为$$$32$$$。