Polygon of Boxes

Taki's attempt to make identical pizzas failed miserably! To help himself forget about it, Takis decided to play with some pizza boxes. Specifically, he has bought ~N~ boxes shaped like rectangular prisms. The ~i~-th box has width ~w_i~ and height ~h_i~.

Initially, Takis placed the first box on the floor, then placed the second box on top of it, and so on, creating a tower. The boxes were placed in such an orientation that the sides of length ~w_i~ were parallel to the ground. Furthermore, since Takis is a perfectionist, he made sure that his tower has a vertical axis of symmetry, as shown in the following diagram.

\<style> .center { display: block; margin-left: auto; margin-right: auto; /*width: 60%;*/ } \</style>

\<img src="https://dmoj.makerlab.gr/static/pdp/pdp2025a2-figure-1.svg" alt="pdp2025a2-figure-1.svg" class="center">

Taki asks you to calculate the perimeter of the shape that is formed, since he got dizzy from all the numbers when he tried to do it himself.

Problem

Write a program in one of the PDP (PASCAL, C, C++, JAVA) programming languages that reads the input data from the file polybox.in and prints the results to the file polybox.out.

Input Files (polybox.in)

The first line contains the subtask number (see below). The second line contains an integer ~N~: the number of boxes. The next ~N~ lines each contain two integers ~w_i~ and ~h_i~, separated by a space: the width and height of the ~i~-th box. The boxes are given in the order in which they are placed in Taki's tower, from bottom to top.

Output Files (polybox.out)

It must contain a single line with an integer: the perimeter of the shape that was formed.

Sample input - output files:

Input:

3
3
6 1
4 2
9 1

Output:

30

Explanation: The example corresponds to the diagram above. The bottom box has width ~6~ and height ~1~, the middle box has width ~4~ and height ~2~, and the top box has width ~9~ and height ~1~. One can calculate, also with the help of the diagram, that the perimeter of this shape is equal to ~30~.

Constraints

• ~1 \le N \le 100.000~
• ~1 \le w_i, h_i \le 10^{40}~

Subtasks:

1. (5 points) ~w_1 = w_2 = ... = w_N~ (all widths are equal), ~w_i \le 10^9~ and ~h_i \le 10^9~
2. (25 points) ~N \le 2~, ~w_i \le 10^9~ and ~h_i \le 10^9~
3. (60 points) ~w_i \le 10^9~ and ~h_i \le 10^9~
4. (10 points) There are no further constraints

Notes

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~2~ sec.
• Maximum available memory: ~128~ MB.
• Source code headers: At the beginning of your source code, you must use the following headers.

(* USER: username
LANG: PASCAL
TASK: polybox *)

for PASCAL code

/* USER: username
LANG: C
TASK: polybox */

for C code

/* USER: username
LANG: C++
TASK: polybox */

for C++ code

/* USER: username
LANG: Java
TASK: polybox */

for Java code

Warning: The answer may exceed ~2^{32}~. Also, make sure to read the input and print the output efficiently, especially if you are translating to C++ or Java.