Tiling the Cathedral Left Partition

You are given a simple axis‐aligned polygon (the "cathedral") with N vertices. The vertices are given in order as \((x_i,y_i)\) for \(i=1,2,\dots,N\) and the polygon has edges between \(i\) and \(i+1\) (for \(1 \le i < N\)) and an edge between \(N\) and 1. Furthermore, every edge is parallel to either the \(x\)–axis or the \(y\)–axis.

You have an unlimited number of \(2\times 2\) square tiles. You want to cover exactly the left‐side part of the cathedral with these tiles. More precisely, for any integer \(k\), let \(L_k\) be the vertical line defined by \(x=k\). A placement of tiles is considered a valid covering of the \(L_k\) left–side of the cathedral if all the following conditions hold:

• Every point which is strictly inside the cathedral and with \(x<k\) is covered by some tile.
• No point outside the cathedral, or any point with \(x>k\), is covered by any tile.
• The interiors of the tiles do not overlap.

It is known that the minimum \(x\)–coordinate among the polygon’s vertices is \(0\) and if we let \(M\) be the maximum \(x\)–coordinate among the vertices then \(0\le k\le M\). Your task is to find the maximum integer \(k\) for which there exists a valid covering of the \(L_k\) left–side of the cathedral. By the problem definition an answer of \(0\) always exists.

Note: Tiles must be placed with their sides parallel to the coordinate axes, and they cannot be rotated.

inputFormat

The first line contains a single integer \(N\) (number of vertices).

Each of the following \(N\) lines contains two integers \(x_i\) and \(y_i\), representing the coordinates of the \(i\)–th vertex of the polygon, given in order.

outputFormat

Output a single integer: the maximum integer \(k\) \((0\le k\le M)\) for which the \(L_k\) left–side of the cathedral can be covered by non–overlapping \(2\times2\) tiles satisfying the conditions.

sample

4
0 0
4 0
4 4
0 4

4