最后的舞会

题目描述

老师为即将毕业的同学们准备了一场舞会，有$2N$个同学会参加这场舞会，他们会被分成$N$对跳舞，每个人有一个编号，如果编号为$i$的同学和编号为$j$的同学配对，那么这一对的满意度是$A_{i,j}(i < j)$，我们规定这个舞会的满意度为每一队的满意度的异或和，也就是说，当同学们分成$N$组后，第$i$对同学的满意度为$A_i$，那么舞会的满意度为$A_1\oplus A_2\oplus...A_N$

请你求出本场舞会满意度的最大值

输入格式

第一行给出一个数$N$，有$2N$个人参加舞会

接下来给出一个矩阵表示$i$和$j$配对时的满意度

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

$A_{2,3},...A_{2,2N}$

$.\\$ $.\\$ $.\\$

$A_{2N-1,2N}$

其中$1\le N \le 8, 0\le A_{i,j} \le 2^{30}$

输出格式

输出本场舞会满意度的最大值

样例输入

2
4 0 1
5 3
2

样例输出

6

样例解释

如果$\{1,2\},\{3,4\}, ans = A_{1,2}\oplus A_{3,4} = 4\oplus 2 = 6$

如果$\{1,3\},\{2,4\}, ans = A_{1,3}\oplus A_{2,4} = 0\oplus 3 = 3$

如果$\{1,4\},\{2,3\}, ans = A_{1,4}\oplus A_{2,3} = 1\oplus 5 = 4$

最后答案为$\max(6,3,4) = 6$