Score : $400$ points

问题描述

设有编号为 $1, 2, \ldots, 2N$ 的 $2N$ 人参加一场舞会。他们将分成 $N$ 对进行舞蹈。

若第 $i$ 个人和第 $j$ 个人配对，其中 $i$ 小于 $j$，则这对的 亲和度 为 $A_{i, j}$。 若这 $N$ 对的亲和度分别为 $B_1, B_2, \ldots, B_N$，则舞会的 总乐趣值 是它们的按位异或运算结果：$B_1 \oplus B_2 \oplus \cdots \oplus B_N$。

请输出在 $2N$ 人可以自由组合成 $N$ 对的情况下，舞会的最大可能总乐趣值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

$2N$ people numbered $1, 2, \ldots, 2N$ attend a ball. They will group into $N$ pairs and have a dance.

If Person $i$ and Person $j$ pair up, where $i$ is smaller than $j$, the affinity of that pair is $A_{i, j}$.
If the $N$ pairs have the affinity of $B_1, B_2, \ldots, B_N$, the total fun of the ball is the bitwise XOR of them: $B_1 \oplus B_2 \oplus \cdots \oplus B_N$.

Print the maximum possible total fun of the ball when the $2N$ people can freely group into $N$ pairs.

Constraints

• $1 \leq N \leq 8$
• $0 \leq A_{i, j} < 2^{30}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$ $\cdots$ $A_{1, 2N}$

$A_{2, 3}$ $A_{2, 4}$ $\cdots$ $A_{2, 2N}$

$A_{3, 4}$ $\cdots$ $A_{3, 2N}$

$\vdots$

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

Output

Print the maximum possible total fun of the ball.

Sample Input 1

2
4 0 1
5 3
2

Sample Output 1

6

Let $\lbrace i, j\rbrace$ denote a pair of Person $i$ and Person $j$. There are three ways for the four people to group into two pairs, as follows.

• Group into $\lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace$. The total fun of the ball here is $A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6$.
• Group into $\lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace$. The total fun of the ball here is $A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3$.
• Group into $\lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace$. The total fun of the ball here is $A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4$.

Therefore, the maximum possible total fun of the ball is $6$.

Sample Input 2

1
5

Sample Output 2

5

There will be just a pair of Person $1$ and Person $2$, where the total fun of the ball is $5$.

Sample Input 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

Sample Output 3

1073289207

update @ 2024/3/10 10:13:46