Airplane Passengers

Every weekend a plane flies from Bitland to Vilnius, and its passengers are extremely demanding: they keep asking the crew for tea, a pillow, and so on. A single flight attendant must fulfill every request.

The rows of the cabin are numbered $1, 2, 3, \dots$. The attendant starts the flight (at minute $0$) standing at row $1$. Walking from one row to an adjacent row takes exactly $1$ minute, and fulfilling a request itself takes no time (it is instantaneous).

Each request is given by two integers $(a, b)$: the passenger sits in row $a$, and the request is made no earlier than minute $b$. Time is measured in minutes, starting from minute $0$ at the beginning of the flight. A request may be fulfilled at minute $b$ or at any later minute, but never before minute $b$. To fulfill a request, the attendant must be standing in that passenger's row at a time of at least $b$.

The attendant may finish the flight standing at any row. Planning her movements optimally, find the minimum number of minutes needed to fulfill every request.

The first line contains the number of requests $N$.

Each of the next $N$ lines contains two integers $a_i$ and $b_i$ separated by a space, describing one request. Here $a_i$ is the number of the row where the passenger sits, and $b_i$ is the earliest time at which the $i$-th request may appear (it may be fulfilled later than this).

Print a single integer: the minimum number of minutes the attendant needs in order to fulfill every request.

• $1 \le N \le 1000$
• $1 \le a_i, b_i \le 10^6$