На бесконечном листе бумаги находится квадратная печать размером \(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\).
Обратите внимание, что вы не ставите печать в левом нижнем углу листа. Обратитесь к примечаниям для лучшего понимания.
Можно доказать, что после всех операций цветная фигура на бумаге, сформированная печатями, представляет собой единую связанную область. Найдите периметр этой цветной фигуры.
Выходные данные
Для каждого набора входных данных выведите одно целое число — периметр цветной фигуры на бумаге.
Примечание
В первом наборе входных данных печать имеет длину стороны \(3\) и нажимается \(4\) раза на координатах \((1, 1)\), \((3, 3)\), \((5, 4)\) и \((6, 6)\). После этого лист бумаги выглядит так:
Здесь квадрат, образованный первым нажатием, окрашен в синий цвет, вторым — в красный, третьим — в зеленый, а четвертым — в фиолетовый. Объединённая фигура, периметр которой нам нужно вычислить, выглядит следующим образом:
Периметр этой фигуры равен \(32\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
32
8
96
|