The Last Dance

Problem Description

The teacher is throwing a farewell dance for the graduating students. $2N$ students will attend and be paired into $N$ dancing couples. Each student has a number; if student $i$ is paired with student $j$, the satisfaction of that couple is $A_{i,j}$ (for $i < j$). The satisfaction of the whole ball is defined as the XOR sum of the satisfaction of every couple: after the students are split into $N$ groups, with the $i$-th couple having satisfaction $A_i$, the ball's satisfaction is $A_1 \oplus A_2 \oplus \dots \oplus A_N$.

Find the maximum possible satisfaction of the ball.

Input Format

The first line gives $N$: there are $2N$ students at the dance.

Then follows a matrix giving the satisfaction when $i$ and $j$ are paired:

A_{1,2}, A_{1,3}, ... A_{1,2N}
A_{2,3}, ... A_{2,2N}
...
A_{2N-1,2N}

where $1 \le N \le 8$ and $0 \le A_{i,j} \le 2^{30}$.

Output Format

Output the maximum possible satisfaction of the ball.

Sample Input

2
4 0 1
5 3
2

Sample Output

6

Sample Explanation

• If $\{1,2\}, \{3,4\}$: $\mathit{ans} = A_{1,2} \oplus A_{3,4} = 4 \oplus 2 = 6$
• If $\{1,3\}, \{2,4\}$: $\mathit{ans} = A_{1,3} \oplus A_{2,4} = 0 \oplus 3 = 3$
• If $\{1,4\}, \{2,3\}$: $\mathit{ans} = A_{1,4} \oplus A_{2,3} = 1 \oplus 5 = 4$

The answer is $\max(6, 3, 4) = 6$.