分数: 400 点
问题陈述
2N 人数 1, 2, \ldots, 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 对。
约束
- 1 \leq N \leq 8
- 0 \leq A_{i, j} < 2^{30}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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}
输出
打印球的最大可能总乐趣。
示例输入 1
2 4 0 1 5 3 2
示例输出 1
6
让 \lbrace i, j\rbrace 表示一对 Person i 和人 j。 将四个人分成两对有以下三种方法。
- 分组为 \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace。 这里球的全部乐趣是 A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
- 分组为 \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace。 这里球的全部乐趣是 A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
- 分组为 \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace。 这里球的全部乐趣是 A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.
因此,球的最大可能总乐趣是 6.
示例输入 2
1 5
示例输出 2
5
只会有一对 Person 1 和人 2,球的全部乐趣在于 5.
示例输入 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
示例输出 3
1073289207