题目描述

举办 BOI2004 的青年旅社有一个停车场，由 $6\times 6$ 的方格组成。行从 $1$ 到 $6$ 从上到下连续编号；列从左到右，编号方法相同。

只有停车场第三排第六列有一个出口。

在那个停车场上，有 $n$ 辆停着的车。你的车在这些车中，但不幸的是，由于你的车被另一辆车挡住了，你的汽车不能直接出去。你与你的朋友可以移动汽车。但是无论是你自己的车还是其他车都不能转向或转弯。

你需要确定使你的 $2\times 1$ 方格车（编号为 $1$）离开停车场所需的最小步数。一步意味着把一辆车移到一个正方形。其他车辆不得驶离停车场。

只有两种车：

• $2\times 1$
• $3\times 1$

汽车只能沿它长的一条边所在的轴移动。

输入格式

第一行一个数 $n$。

接下来 $n$ 行，每行四个数 $l,opt,x,y$，分别表示汽车长度、停放的方向、汽车左上角坐标。

输出格式

仅一行一个数，即使车离开停车场所需的最小步数。

如果不能，输出 -1。

8
2 1 2 3
2 1 1 1
2 0 1 5
2 1 5 5
3 0 6 1
3 0 1 2
3 0 4 2
3 1 3 6

18

提示

样例 1 说明

步骤（编号 $+$ 移动步骤）：

• $4\gets\gets\gets$
• $2\to$
• $6\uparrow$
• $3\uparrow$
• $8\gets\gets$
• $5\downarrow\downarrow\downarrow$
• $7\downarrow\downarrow$
• $1\to\to\to\to\to$

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 16$，$opt\in\{0,1\}$，$l\in\{2,3\}$，$1\le x,y\le 6$。

说明

译自 BalticOI 2004 Day2 C CAR PARK