오벨리스크

건설 현장은 $K$개의 층으로 이루어져 있고, 각 층은 무한히 넓은 격자다. 맨 아래 층을 뺀 모든 층에는 한 칸 크기의 구멍이 여러 개 뚫려 있다. 맨 아래 층에는 X로 표시된 칸이 하나 있다.

크기가 $1 \times 1 \times M$인 무거운 직육면체 오벨리스크가 맨 위 층에 똑바로 세워져 있다. 작업자들은 이 오벨리스크를 X로 표시된 칸 위에 $1 \times 1$ 면이 닿도록 똑바로 세우려고 한다.

오벨리스크는 너무 무거워서 밀거나 들어 올릴 수 없다. 옮기는 방법은 바닥에 닿아 있는 모서리 하나를 축으로 90도 넘어뜨리는 것뿐이다. 한 번 넘어뜨리는 것을 한 번의 이동으로 센다.

그림 1: 크기가 $1 \times 1 \times 2$인 오벨리스크를 굴리는 모습

아래 층으로 내려가려면 오벨리스크를 구멍 위에 올려야 한다. 그러면 오벨리스크가 아래 층으로 떨어진다. 떨어지는 데는 이동 횟수를 쓰지 않고, 떨어지는 동안에도 오벨리스크는 똑바로 선 자세를 유지한다.

그림 2: 구멍으로 떨어지는 오벨리스크

오벨리스크는 바닥에 닿은 칸이 모두 구멍일 때만 떨어진다. 같은 층에서 두 구멍이 변을 맞대는 일은 없으므로, $M$이 2 이상이면 누운 오벨리스크는 절대 떨어지지 않는다. 즉 $M$이 2 이상일 때는 구멍 위에 똑바로 섰을 때만 떨어진다. $M$이 1이면 구멍에 올라서는 순간 떨어진다. 서로 다른 층의 구멍이 수직으로 겹칠 수도 있고, 이때 오벨리스크는 구멍이 아닌 칸을 만날 때까지 여러 층을 연달아 떨어진다.

구멍이 오벨리스크의 이동을 막지는 않는다. 오벨리스크의 모서리는 항상 격자에 맞춰져 있고, 처음에 오벨리스크는 맨 위 층의 구멍이 아닌 칸 위에 똑바로 세워져 있다.

맨 위 층의 처음 위치에서 맨 아래 층의 X 칸까지 오벨리스크를 옮기는 데 필요한 최소 이동 횟수를 구하여라.

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

둘째 줄에 네 정수 $S_x$, $S_y$, $E_x$, $E_y$가 주어진다. $(S_x, S_y)$는 맨 위 층에서 오벨리스크가 처음 서 있는 칸이고, $(E_x, E_y)$는 맨 아래 층에서 X로 표시된 칸이다.

이어지는 $K - 1$개의 줄은 맨 위 층부터 아래에서 두 번째 층까지 각 층의 구멍을 위에서부터 차례로 알려 준다. 각 줄은 그 층의 구멍 개수 $h$로 시작하고, 그 뒤에 $2h$개의 정수 $x_1$ $y_1$ $x_2$ $y_2$ $\dots$ $x_h$ $y_h$가 공백으로 구분되어 주어진다. $(x_i, y_i)$는 그 층에 있는 구멍의 좌표다. 맨 아래 층을 뺀 모든 층에는 구멍이 적어도 하나 있다.

제한:

• $2 \le K \le 10$
• $1 \le M \le 5$
• $1 \le S_x, S_y, E_x, E_y \le 30$
• $1 \le h \le 450$, $1 \le x_i, y_i \le 30$
• 같은 층의 구멍은 서로 다르고, 변을 맞대는 두 구멍은 없다.
• $(S_x, S_y)$는 맨 위 층의 구멍이 아니다.
• 각 층은 무한히 넓으므로 오벨리스크는 위 좌표 범위 밖으로도 굴러갈 수 있다.

X로 표시된 칸 위에 오벨리스크를 똑바로 세우는 데 필요한 최소 이동 횟수를 한 줄에 출력한다. 옮길 수 없으면 -1을 출력한다.