광장 달리기

Runsberg 시민들은 스포츠, 특히 달리기를 좋아한다. 평범한 마라톤이 지루해진 시민들은 마인크래프트 방식의 마라톤을 열기로 했다. 행사는 Runsberg 중앙 광장에서 열린다. 시민들은 스포츠에서 가장 중요한 것은 이기는 것이 아니라 참가하는 것이라고 믿는다. 그래서 광장 달리기의 목표는 우승이 아니라 모든 참가자의 아름다운 사진을 찍는 것이다.

중앙 광장은 단위 정사각형으로 나뉜 직사각형이다. 행은 위에서 아래로 1부터, 열은 왼쪽에서 오른쪽으로 1부터 번호가 붙는다. 각 단위 정사각형의 좌표는 행 번호 $r$과 열 번호 $c$로 나타낸다.

광장에는 변이 광장의 변과 평행한 직사각형 잔디밭이 있다. 잔디밭의 왼쪽 위 칸은 $(R_L, C_L)$, 오른쪽 아래 칸은 $(R_R, C_R)$이다. 잔디밭 둘레에는 $n$개의 레인이 있다. 레인 $i$는 잔디밭 경계에서 거리 $i$에 있고, 레인 $i$에는 러너 $i$가 있다. 러너 $i$는 칸 $(r_i, c_i)$에서 출발한다. 모든 러너는 같은 시각에 같은 속도로 출발한다. 매초 각 러너는 현재 칸에서 자기 레인의 다음 칸으로 반시계 방향으로 이동한다.

사진사는 잔디밭의 칸 $(R_p, C_p)$에 서 있다. 사진사가 쓰는 이중 렌즈 카메라는 반대 방향 두 곳을 동시에 찍는다. 셔터를 누르는 순간 모든 러너가 행 $R_p$에 있거나 열 $C_p$에 있으면 사진이 아름답다. 이 카메라 덕분에 러너들은 사진사의 왼쪽과 오른쪽에 같은 행으로, 또는 위쪽과 아래쪽에 같은 열로 있을 수 있다.

마라톤 시작 후 사진사가 아름다운 사진을 찍을 수 있는 최소 시간 $t$(초)를 구하라. 이 조건에서 아름다운 사진을 찍을 수 없다면 그 사실을 구하라.

첫 줄에 러너 수 $n$ ($1 \le n \le 18$)이 주어진다. 둘째 줄에는 여섯 정수 $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$), $C_p$ ($C_L \le C_p \le C_R$)가 주어진다. 차례대로 잔디밭의 왼쪽 위 칸, 오른쪽 아래 칸, 사진사의 위치다. $R_R - R_L + C_R - C_L$은 4로 나누어떨어진다고 보장된다.

다음 $n$개 줄에는 러너 $i$의 시작 좌표 $r_i$, $c_i$가 주어진다. 각 시작 좌표는 레인 $i$ 위에 있고, 레인마다 러너는 한 명뿐이며, 레인 $i$는 잔디밭 경계에서 거리 $i$에 있다고 보장된다.

사진사가 아름다운 사진을 찍을 수 있는 마라톤 시작 후 최소 시간 $t$(초)를 출력한다. 이 조건에서 불가능하면 -1을 출력한다.

러너들의 시작 위치다.

3초 후 러너들의 위치다. 모든 러너가 행 $R_p$에 있으므로 사진사는 아름다운 사진을 찍을 수 있다.