회로를 n * n 의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 가장 자리에 있는 격자를 제외하고 상,하,좌,우 4 개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다. 아래 그림에서는 X 와 Y , P 와 Q 를 연결한 두개의 회로가 있다. 이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때, 이들 두 격자를 잇는 새로운 회로를 배치하려고 한다.

새로 배치될 회로는 이미 회로가 배치된 격자 위에 배치될 수 도 있다. 이 회로의 배치비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다. 회로가 배치되지 않은 빈 격자를 지나는 비용은 1 이고, 이미 회로가 놓여 있는 격자를 지날 때는 비용이 k ( k >= 2) 이다. 주어진 문제는 최소의 비용이 소요되는 새로운 회로를 찾는 것이다.

예를 들어 아래의 그림에서 k 가 4 로 주어진다면, 점선을 따라 격자 A 와 B 를 잇는 회로의 비용은 19 이지만, 비용이 16 인 최소비용 회로가 존재한다. ( 이 비용에는 격자 A,B 의 비용도 포함된다.)

입력 형식

• 첫 째 줄에는 격자 판의 크기를 나타내는 정수 (2 <= n <= 50)가 주어진다.
• 둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4 개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다.(시작 격자와 마지막 격자의 위치는 같을 수 없다.)
• 셋째 줄에는 회로가 배치된 격자를 지나는데 드는 비용인 정수 k 가 주어진다.
• 넷째 줄에는 이미 배치된 회로의 개수가 주어진다.
• 다섯째 줄부터는 한 줄에 한 회로의 배치 정보가 다음과 같이 주어진다. 줄의 첫수는 회로의 행,열의 쌍의 개수이고 다음 부터 회로의 시작 격자, 90^o로 꺽이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수이고, 그 다음부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다.

출력 형식

• 첫째 줄에는 회로의 최소 비용을 출력한다.
• 둘 째줄에는 최소 비용 회로의 정보를 다음과 같이 출력한다.(입력 형식과 동일함) 처음에 회로의 시작 격자,90^o로 꺽이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력하고,
• 그 다음 부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다.

입력과 출력의 예

입력

11
2 3 9 8
4
2
3 3 9 3 4 10 4
4 9 2 7 2 7 7 5 7

출력

16
3 2 3 2 8 9 8

출처: koi 중등부 기출
special judge:conankun