주차장

BOI2004가 열리는 유스호스텔에는 6 곱하기 6 격자로 이루어진 주차장이 있다. 주차장의 행은 위에서 아래로 1부터 6까지 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 같은 방식으로 번호가 매겨진다. 주차장의 출구는 3행 오른쪽에 하나뿐이다.

이 주차장에는 N대의 차가 주차되어 있다. 당신의 차도 그중 하나인데, 다른 차들에 가로막혀 있어서 쉽게 빠져나갈 방법이 없다. 당신과 친구들은 차를 앞뒤로 움직일 수 있다. 모든 차의 기어가 중립에 놓여 있기 때문이다. 당신의 차든 다른 차든 조향하거나 회전할 수는 없다.

당신의 임무는 크기 2x1 칸인 당신의 차를 주차장 밖으로 빼내는 데 필요한 최소 이동 횟수를 구하는 것이다. 한 번의 이동은 한 차를 한 칸 움직이는 것을 뜻한다. 다른 차는 주차장 밖으로 나갈 수 없다.

차는 두 종류뿐이다. 한 종류는 크기가 2x1 칸이고, 다른 종류는 3x1 칸을 차지한다. 차는 두 축 중 더 긴 축을 따라서만 움직일 수 있다.

주어진 예에서 N = 8이고 당신의 차에는 1번이 붙어 있다.

다음은 당신의 차로 주차장을 빠져나가는 길이 18인 최소 이동 순서이다: 4←←←, 2→, 6↑, 3↑, 8←←, 5↓↓↓, 7↓↓, 1→→→→→.

입력의 첫째 줄에는 차의 수 N(1 ≤ N ≤ 16)이 주어진다.

그다음 N개 줄에는 각각 i번이 붙은 차의 설명이 주어진다. 각 줄은 길이 li, 방향 oi, 시작점(왼쪽 위)의 좌표 xi(열 번호)와 yi(행 번호)를 나타내는 네 정수로 이루어진다. 인접한 수는 공백 문자 하나로 구분된다. oi = 1이면 차가 가로로 주차되어 있다는 뜻이다.

그렇지 않으면 세로로 주차되어 있다. 다음 제한이 적용된다: li ∈ {2, 3}, oi ∈ {0, 1}, 1 ≤ xi, yi ≤ 6.

당신의 차는 N이 적힌 한 줄 바로 다음 줄에 설명된다(즉 입력 파일의 둘째 줄). 당신의 차는 유일한 출구를 이용해 주차장을 빠져나가야 한다.

출력은 하나의 정수만으로 이루어져야 하며, 당신의 차로 주차장을 빠져나가는 데 필요한 최소 이동 횟수를 나타낸다.

주차장을 빠져나갈 수 없다면 -1을 출력한다.