Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits
Description
相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。
一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。
后来，随着人们认知水平的提高，这个现象得到了很好的解释。经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来为零。 （如果你不清楚什么是异或，请参见下一页的名词解释。 ）例如，使用两个同样的矿石必将发生“魔法抵消”，因为这两种矿石的元素序号相同，异或起来为零。
并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。
现在，给定你以上的矿石信息，请你来计算一下当时可以炼制出的法杖最多有多大的魔力。
Input
第一行包含一个正整数N，表示矿石的种类数。
接下来 N行，每行两个正整数Numberi 和 Magici，表示这种矿石的元素序号和魔力值。
Output
仅包含一行，一个整数：最大的魔力值。
Sample Input
【Case 1】
3
1 10
2 20
3 30
【Case 2】
7
5 5
3 20
9 40
10 30
5 10
6 10
5 10
Sample Output
【Case 1】
50
【Case 2】
80
Hint
【样例 1 说明】
由于有“魔法抵消”这一事实，每一种矿石最多使用一块。
如果使用全部三种矿石，由于三者的元素序号异或起来：1 xor 2 xor 3 = 0 ，
则会发生魔法抵消，得不到法杖。
可以发现，最佳方案是选择后两种矿石，法力为 20+30=50。
【样例 2 说明】
一个最佳方案是：选择第 3、4、5 种矿石。
注意：可能有一些矿石，它们有相同的元素序号。
【数据规模】
对于 30%的数据：N ≤ 10；
另外有 40%的数据：Numberi 在二进制表示下恰好有两位是1，如样例 2；
对于全部的数据：N ≤ 1000，Numberi ≤ 1018，Magici ≤ 104。
【名词解释】
异或（exclusive disjunction）是一种逻辑运算，满足：
0 xor 0 = 0 0 xor 1 = 1 1 xor 0 = 1 1 xor 1 = 0
按位异或即：将两自然数在二进制下表示，每一位进行以上的运算。
在 C/C++中，该操作对应为 “^” ；在 Pascal中，该操作对应为“xor”。
容易发现，自然数集中的该运算构成 Abel群（满足交换律、结合律）
Solution
线性基+贪心
我们需要用线性基来维护我们选取的非空子集中不存在异或出结果为0的情况
然后还需要满足最后得到的权值最大
根据异或的性质我们不难想到可以根据贪心来求解
我们将每件物品按照权值从大到小排序，然后不断插入线性基中累加答案即可
Code
#include<algorithm>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=1e3+5;
int n;
ll ans,p[63];
struct node
{
ll num;
int val;
}a[N];
bool cmp(node x,node y)
{
return x.val>y.val;
}
int main()
{
scanf("%d",&n);
fo(i,1,n) scanf("%lld%d",&a[i].num,&a[i].val);
sort(a+1,a+1+n,cmp);
fo(i,1,n)
{
fd(j,62,0)
if((a[i].num>>j)&1)
{
if(!p[j])
{
p[j]=a[i].num;
break;
}
a[i].num^=p[j];
}
if(a[i].num) ans+=a[i].val;
}
printf("%lld",ans);
}