Page not loading? Try clicking here.
Placeholder

#1033
Special judge

회로배치 1s 128MB

Problems

We want to place a circuit on an n \times n grid board. 

Here, each grid (square cell) has four neighboring grids (up, down, left, and right), except for the grids on the edges. 

A circuit is a path of consecutive neighboring grids with a start and an end. 

In the figure below, there are two circuits connecting X and Y,\ P and Q. 

Given the two end grids of a new circuit to be placed on a grid board where circuits are already placed, 

we want to place a new circuit connecting these two grids.

 

The new circuit to be placed may be placed on top of grids where circuits are already placed. 

The placement cost of this circuit is determined as follows, depending on the grids the circuit passes through. 

The cost of passing through an empty grid where no circuit is placed is 1, 

and the cost of passing through a grid where a circuit is already placed is k(k≥2). 

The given problem is to find a new circuit that incurs the minimum cost.

 

For example, if k is given as 4 in the figure below, 

the cost of the circuit connecting grids A and B along the dotted line is 19, but there exists a minimum cost circuit with a cost of 16.

(This cost also includes the costs of A\ B.)


Input

The first line of the input contains an integer n representing the size of the grid board. (1≤n≤50)

The second line contains 4 integers representing the positions of the starting grid and the ending grid of the circuit to be newly placed. The position of a grid is given in the order of the row and column numbers shown in the figure above. (The starting and ending grid positions cannot be the same and cannot overlap with already placed circuits.) 

The third line contains an integer k, which is the cost of passing through a grid where a circuit is already placed. (2 \le k \le 100)

The fourth line contains the number of already placed circuits. 

From the fifth line onwards, the placement information for one circuit per line is given as follows. 

The first integer is the total number of the circuit's starting grid, the grids where it turns 90°, and the ending grid,

and from then on, the positions of these grids are given in the order of row and column from the starting grid to the ending grid.


Output

On the first line, output the minimum cost of the circuit. 

On the second line, output the information of the minimum cost circuit as follows.

(Same as the input format) First, output the total number of the starting grid, the grids where the direction changes by 90°, and the last grid. 

Then, output the positions of these grids from the starting grid to the last grid, one by one in the order of row and column, separated by a space.


Example 

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

Source

KOI 전국 1999 중2

You must sign in to write code.