2018 程序设计能力实训第三次机考

E. 整数分组

单点时限: 2.0 sec

内存限制: 256 MB

将 $n$ 个正整数分成两组,使得每一组内整数的二进制无进位之和 (记为⊕) 相等。

找出满足以上条件的一种分组方法,使得其中一组的所有整数之和最大。

二进制无进位之和的例子: 1100B⊕0101B=1001B (即12⊕5=9), 其中第0,1,3位加没有进位,第2位1+1=10,但1不做进位处理。

例如:有三个数3,5,6,分成{3}一组,{5,6}一组。因为5⊕6=3,满足条件的整数之和最大的一组就是{5,6}。

输入格式

第1行:整数 $n$ 。

第2行:$n$ 个由一个空格分隔的正整数。

80%的数据点: $2 \leq n \leq 1000 $, 每个整数不大于 $10^6$

10%的数据点: $ 2 \leq n \leq 1000 $, 每个整数不大于 $10^{12}$

10%的数据点: $ 2 \leq n \leq 10000 $, 每个整数不大于 $10^{18}$

输出格式

在一行中输出满足条件的整数之和最大的一组的所有整数之和。若找不到满足条件的分组方法,输出-1。

样例

Input
3
3 5 6
Output
11
Input
3
3 5 7
Output
-1
Input
2
1000000 1000000
Output
1000000