오벨리스크 Batch 컴파일 명령

한 건축 부지는 $K$개의 층으로 구성되어 있으며, 각 층은 무한히 넓은 격자판으로 나타낼 수 있습니다. 최하층을 제외한 각 층에는 정사각형 하나 크기의 구멍이 몇 개 뚫려 있습니다. 최하층에는 X로 표시된 격자가 하나 있습니다. 또한 무거운 직육면체 형태의 오벨리스크가 있습니다. 이것의 크기는 $1 \times 1 \times M$이며, 초기에 위쪽을 향하도록 최상층에 놓여 있습니다. 노동자들은 이 오벨리스크를 지면과 수직하게 세워서 $1 \times 1$ 크기의 면이 X로 표시된 격자 위에 놓이도록 하고자 합니다.

이 오벨리스크는 밀거나 들고 가기에는 너무 무거워서, 노동자들이 이를 옮길 방법은 단지 이 오벨리스크를 굴리는 것밖에 없습니다. 굴리는 방식은 아래 [그림 1]에서 볼 수 있습니다.

[그림 1] $1 \times 1 \times 2$ 크기의 오벨리스크를 굴리는 모습

오벨리스크를 아랫층으로 옮기기 위해, 노동자들은 오벨리스크를 구멍 위로 굴려 [그림 2]와 같이 더 낮은 층으로 떨어지도록 해야 할 것입니다.

[그림 2] 구멍을 통해 아랫층으로 떨어지는 오벨리스크

위에서 명시했듯이, 각 구멍의 크기는 $1 \times 1$입니다. 각 층에서 어떤 두 개의 구멍도 인접한 격자에 위치하지 않습니다. 따라서, 만약 오벨리스크가 지면과 수평하게 놓여 있다면, $M$이 1이 아닌 이상 아랫층으로 떨어질 일은 없습니다. 그러나, 두 개 이상의 구멍이 여러 개의 층에서 같은 위치에 위치해 있을 수도 있습니다. 이 경우 오벨리스크는 구멍이 아닌 격자에 착지하기 전까지 계속 떨어질 것입니다.

오벨리스크는 초기에 크기가 $1 \times 1$인 면이 격자판과 마주보도록 놓여 있으며, 이 면이 있는 격자에는 구멍이 뚫려 있지 않습니다.

여러분이 할 일은 이 오벨리스크를 초기 위치에서부터 최하층에 위치한 X로 표시된 격자에 놓기 위해 오벨리스크를 굴려야 할 최소 횟수를 구하는 것입니다.

입력 형식

첫 번째 줄에는 층 수 $K$와 오벨리스크의 높이 $M$이 주어집니다.

두 번째 줄에는 오벨리스크의 초기 위치의 좌표 $S_{x}, S_{y}$와 X로 표시된 격자의 좌표 $E_{x}, E_{y}$가 주어집니다. 초기에 오벨리스크는 최상층에 위치해 있으며 X 격자는 최하층에 위치해 있습니다.

다음 $K-1$개 줄에는 각 층에 뚫려 있는 구멍의 정보가 최상층, 위에서 2번째 층, ..., 최하층 바로 윗층 순서대로 주어집니다. 각 줄에는 해당 층에 뚫려 있는 구멍의 수 $h$가 주어지며, 이후 구멍들의 위치를 나타내는 $2h$개의 정수 $x_{1}, y_{1}, x_{2}, y_{2} \cdots, x_{h}, y_{h}$가 공백을 사이로 두고 주어집니다. 각 $i$에 대해, $x_{i}$와 $y_{i}$는 이 층에 뚫려 있는 구멍의 $x$좌표와 $y$좌표를 나타냅니다. 최하층을 제외한 모든 층에는 구멍이 적어도 1개 뚫려 있다는 점에 유의하세요.

출력 형식

오벨리스크를 지정된 위치로 옮기기 위해 굴려야 할 최소 횟수를 출력합니다. 만약 이것이 불가능하다면 -1을 출력합니다. 답은 32비트 정수로 나타낼 수 없을 수도 있으니, C/C++에서 long long의 사용을 권장합니다.

서브태스크

1. (5점) $M = 1$, $1 \le K \le 10$. 모든 좌표는 50 이하의 자연수입니다. 각 층에는 최대 10개의 구멍이 뚫려 있습니다.
2. (7점) $1 \le M \le 50$, $1 \le K \le 10$. 모든 좌표는 50 이하의 자연수입니다. 각 층에는 최대 100개의 구멍이 뚫려 있습니다.
3. (6점) $1 \le M \le 400$, $1 \le K \le 500$. 모든 좌표는 400 이하의 자연수입니다. 각 층에는 최대 100개의 구멍이 뚫려 있습니다.
4. (7점) $1 \le M \le 100000$, $1 \le K \le 500$. 모든 좌표는 1,000,000,000 이하의 자연수입니다. 각 층에는 최대 100개의 구멍이 뚫려 있습니다.

예제