JUNGOL

회로를 n \times n의 격자 판에 배치하려고 한다.

여기서 각 격자(정사각형 칸)는 가장자리에 있는 격자를 제외하고 상 하 좌 우 4개의 이웃 격자를 갖는다.

회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다.

아래 그림에서는 X와 Y,\ P와 Q를 연결한 두 개의 회로가 있다.

이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때,

이들 두 격자를 잇는 새로운 회로를 배치하려고 한다.

새로 배치될 회로는 이미 회로가 배치된 격자 위에 배치될 수도 있다.

이 회로의 배치 비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다.

회로가 배치되지 않은 빈 격자를 지나는 비용은 1이고,

이미 회로가 놓여있는 격자를 지날 때는 비용이 k(k≥2)이다.

주어진 문제는 최소의 비용이 소요되는 새로운 회로를 찾는 것이다.

예를 들어 아래의 그림에서 k가 4로 주어진다면,

점선을 따라 격자 A와 B를 잇는 회로의 비용은 19이지만 비용이 16인 최소비용 회로가 존재한다.

(이 비용에는 A\ B의 비용도 포함된다.)

Entrada

입력의 첫째 줄에는 격자 판의 크기를 나타내는 정수 n이 주어진다. (1≤n≤50)

둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다. (시작 격자와 마지막 격자의 위치는 같을 수 없고, 이미 배치된 회로와 겹칠 수 없다.)

셋째 줄에는 회로가 배치된 격자를 지나는데 드는 비용인 정수 k가 주어진다. (2 \le k \le 100)

넷째 줄에는 이미 배치된 회로의 개수가 주어진다.

다섯째 줄부터는 한 줄에 한 회로의 배치 정보가 다음과 같이 주어진다.

첫째 정수는 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들 그리고 마지막 격자의 총 개수이고,

그 다음부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다.

Salida

첫째 줄에는 회로의 최소 비용을 출력한다.

둘째 줄에는 최소 비용 회로의 정보를 다음과 같이 출력한다.

(입력 형식과 동일함) 처음에 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력한다.

그 다음부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다.

Ejemplo

Fuente

KOI 전국 1999 중2

회로배치 1s 128MB