Maximum Binary Search Tree on Tetrahedral Triangular Grid

A regular tetrahedron is constructed as follows. First, a regular triangle of side length \(n\) is subdivided into \(n^2\) congruent unit equilateral triangles. For example, when \(n=3\), the triangle is partitioned into 9 unit triangles which are numbered from top to bottom and left to right (as illustrated in the figure).

Four copies of such triangles are used as the faces of a tetrahedron. The three lateral faces are labeled A, B, and C in clockwise order (viewed from the top vertex downwards), and the base is labeled D. On each face the unit triangles are numbered in order starting from the top vertex (which is marked by a dot on faces A, B, and C; for face D the dot is placed at the vertex where it meets faces A and B).

Thus, in total there are \(4n^2\) unit triangles on the tetrahedron. Each unit triangle is assigned a distinct integer from \(1\) to \(4n^2\) at random. Two unit triangles are said to be adjacent if they share a common edge in the folded (3D) state of the tetrahedron (note that adjacency in the unfolded (net) diagram is not used).

A binary search tree (BST) is constructed by selecting some of these unit triangles as nodes and connecting them as follows. When an integer \(i\) is chosen as a node in the BST, its parent (if it exists) and its children (if any) must be located in unit triangles that are adjacent to the unit triangle containing \(i\) (in the tetrahedron). In addition, the BST must satisfy the usual ordering property: for every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater than the node’s value.

Your task is to find the maximum binary search tree (i.e. the one with the greatest number of nodes) that can be formed under these conditions, and output its size (i.e. the number of nodes in the tree).

Note: For the purpose of this problem the geometry of each face is given in a standard manner. The input first gives an integer \(n\), followed by four blocks corresponding to faces A, B, C and D. In each block, the \(n^2\) integers appear in the order described above. It is guaranteed that \(1 \le n \le 50\). (In the actual tests, however, the value of \(n\) will be very small so that a brute-force or backtracking solution can pass.)

inputFormat

The first line contains a single integer \(n\) denoting the side length of each face. This is followed by 4 blocks. Each block contains \(n^2\) integers separated by spaces or newlines, representing the labels of the unit triangles on one face. The blocks appear in the order: face A, face B, face C, then face D.

outputFormat

Output a single integer: the size (number of nodes) of the largest binary search tree that can be formed under the given conditions.

sample

1
1 2 3 4

4