题目描述

在一个 $6 \times 6$ 的正方形网格中停靠着若干辆车。

其中的一号车是学校的班车，长度为 $2$，宽度为 $1$。其它车的宽度为 $1$，长度为 $2$ 或 $3$。

每辆车的朝向是南北向或东西向。

我们可以使某辆车沿着它的朝向移动一步，前提是没有开出网格或者有别的车阻拦。

我们的目的是使一号车从网格的第三行六列右侧的出口离开，在这基础上还要使所有车移动的步数之和最小。

输入格式

第一行是车的数目 $n$。

此后 $n$ 行，第 $i$ 行有四个整数 $l_i,o_i,x_i,y_i$。

$l_i∈\{2,3\}$，表示第 $i$ 辆车的长度。

$o_i ∈\{0,1\}$，表示第 $i$ 辆车的方向。若 $o_i=0$，表示第 $i$ 辆车是南北朝向；若 $o_i=1$，表示第 $i$ 辆车是东西朝向。

$(x_i,y_i)$ 表示第 $i$ 辆车的左上角处于网格第 $y_i$ 行第 $x_i$ 列的位置。

输出格式

仅含一个整数，表示把班车开出网格需要的最小步数。

如果无解就输出 $-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

数据规模与约定

对于 $100\%$ 的数据，$n\leq16$，$l_i\in\{2,3\}$，$o_i\in\{0,1\}$，$1\leq x_i,y_i\leq6$。