Square Running

Runsberg citizens are keen on sports, especially running. Standard marathons bored them, so they decided to organize a marathon in Minecraft style. The event will be held on Runsberg's Central Square. Citizens believe that the most important thing in sports is not winning but participating, so the goal of the square running is not to win but to take a beautiful photo of all participants.

The Central Square is a rectangle divided into unit squares. Rows are numbered from top to bottom starting from one, and columns are numbered from left to right starting from one. Each unit square has coordinates $r$ and $c$, its row and column number.

A rectangular grass field lies on the square, with sides parallel to the square's sides. Its top left unit square is $(R_L, C_L)$, and its bottom right unit square is $(R_R, C_R)$. There are $n$ lanes for $n$ runners around the grass field. Lane $i$ is at distance $i$ from the field's border, and runner $i$ is on lane $i$. Runner $i$ starts from the unit square $(r_i, c_i)$. All runners start at the same time at the same speed. Every second, each runner moves from the current square to the next square in their lane, counterclockwise.

A photographer stands on the unit square $(R_p, C_p)$ of the grass field. The photographer uses a dual-lens camera that takes a photo in two opposite directions at once. A photo is beautiful if, at the moment of the shot, all runners are in row $R_p$ or in column $C_p$. Because of the camera, runners may be in the same row on both the left and right of the photographer, or in the same column above and below.

Find the minimum number of seconds $t$ after the start after which the photographer can take a beautiful photo. If no beautiful photo is possible under these conditions, find that out instead.

The first line contains an integer $n$ ($1 \le n \le 18$), the number of runners. The second line contains six integers $R_L$, $C_L$, $R_R$, $C_R$ ($n + 1 \le R_L \le R_R \le 100 - n$, $n + 1 \le C_L \le C_R \le 100 - n$), $R_p$ ($R_L \le R_p \le R_R$), and $C_p$ ($C_L \le C_p \le C_R$). These are the top left corner, the bottom right corner, and the photographer's position. It is guaranteed that $R_R - R_L + C_R - C_L$ is divisible by 4.

The next $n$ lines each contain two integers $r_i$ and $c_i$, the starting coordinates of runner $i$. Each start lies on lane $i$, each lane holds exactly one runner, and lane $i$ is at distance $i$ from the field's border.

Print the minimum number of seconds $t$ after the start at which the photographer can take a beautiful photo, or $-1$ if that is impossible.

Starting positions of the runners.

Positions of the runners after 3 seconds. All runners are in row $R_p$, so the photographer can take a beautiful photo.