e-olymp
Problems

The Red and Blue Squares

The Red and Blue Squares

Petrik and Vasilko prepare to the coming test "perimeter and area of figures". Petrik drew some geometrical figures. And painted some cells with blue color. Vasilko calculated the perimeter of the figure and drew the maximal number of red squares so that the perimeter of new figure remained the same. Write the program, that for the given coordinates of the painted blue squares finds the most amount of red squares that you can draw in such way, that the perimeter of new figure does not change after the set co-ordinates of the painted out dark blue squares.

prb48

Input

The first line contains the quantity of blue squares n (0 < n < 40404). Each of the next n lines has two numbers x, y (-101x, y101) that contain the coordinates of left lower corners of blue squares.

Every blue square has one common point with at least one of the other blue squares. The figure, formed with blue squares, is connected.

Output

Print the number of red squares.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3
1 2
2 1
3 1
Output example #1
3