Workers of the World Unite! Just Not Too Close.

문제

You are in charge of a set of workers working on a project so top secret we can't even think of a name for it.  They are each housed separately in a set of apartments shown on the left in figure 1 and every morning they each leave at the same time and proceed to one of the workstations shown on the right.  In order to get from their homes to the workstations they must pass through a security gate shown in the middle.  Each gate has two different corridors that can be used, labeled A and B.  As can be seen from the figure the A corridors in each gate are always to the north of the B corridors.

Figure 1: Layout of apartments, gates and workstations.

Getting the workers to the workstations sounds simple, but with the onset of COVID-$1919$ a problem has arisen.  First, because of social distancing no two workers can use the same gate.  Second, because of the layout of the gates, if one worker uses an A corridor, the person using the gate to the north of them cannot use the B corridor -- it's too close.  The analogous thing occurs if a worker uses a B corridor -- the worker using the gate to the south of them can't use the A corridor.

You are in charge of assigning workers to the stations, one worker at each station.  It doesn't matter which worker is assigned to which workstation but you would like to minimize the total distance all the workers travel while adhering to the social distancing requirements described above.  Due to the strange layout of the entrances and exits to the gates there can sometimes be large differences in distances when using the A corridor versus the B corridor for a gate, which complicates the problem.  Given all the relative distances, determine an assignment of workers to workstations that minimizes the total distance everyone travels.

입력

Input begins with a line containing one positive integer $n\le 50n\; \backslash leq\; 50$, specifying the number of workers, gates and workstations, each numbered $11$ to $nn$. Following this are $nn$ lines each containing $2n2n$ positive integers.  The $ii$-th of these lines gives the distance from worker $ii$ to the entrances of the $nn$ gates; the first two values are the distances to corridors A and B for gate $11$, the second two values are the distances to corridors A and B for gate $22$, and so on.  After this are $nn$ more lines each containing $2n2n$ positive integers.  The $jj$-th of these lines gives the distance from the workstation $jj$ to the exits of the $nn$ gates in an analogous fashion.  All distances are positive and $\le 1000\backslash leq\; 1\backslash ;\; 000$.

출력

On the first line of output print the minimum total distance traveled by the workers that can be achieved.  Follow this with $nn$ lines showing the assignment for each worker.  The $ii$-th of these lines will have the form $ii$ $g_{i}g\_i$ $w_{i}w\_i$ indicating that worker $ii$ uses gate $g_{i}g\_i$ to get to workstation $w_{i}w\_i$.  Use the format shown in the sample output. If there are several optimal assignments, any will be accepted

3
75 64 25 9 32 1
72 51 49 46 64 53
13 37 75 35 62 50
90 62 72 6 30 35
39 89 17 62 47 65
94 79 27 93 21 58

163
1 3B 3
2 2B 1
3 1A 2