Maximum Wand Magic Power

In ancient Magic Land, wizards crafted wands using magical minerals. Each mineral has a positive element index (denoted by \(e\)) and an inherent magical power. The magical power of a wand is the sum of the magical powers of the minerals used. However, during the synthesis process, a phenomenon known as magical cancellation occurs if there exists any nonempty subset \(T\) of the chosen minerals such that their element indices, when combined using bitwise XOR, equal zero. In other words, if there exists a nonempty \(T \subseteq S\) with

[ \bigoplus_{x \in T} e(x) = 0, ]

the synthesis will fail. Note that using more than one mineral of the same type (i.e. same element index) will automatically cause cancellation. It can be shown that a set of minerals is free of magical cancellation if and only if the set of their element indices is linearly independent over \(\mathbb{F}_2\) (the field with two elements). Given the information of each mineral discovered, your task is to select a subset that is free from magical cancellation and maximizes the total magical power of the wand.

Note: Minerals with an element index of zero can never be used since a single mineral with index zero would cause cancellation.

inputFormat

The input begins with a single integer \(n\) (the number of minerals). Each of the following \(n\) lines contains two positive integers \(v\) and \(m\), where \(v\) is the element index of the mineral and \(m\) is its magical power.

Note: Minerals with \(v = 0\) are not allowed in a valid synthesis.

outputFormat

Output the maximum total magical power that can be obtained by selecting a subset of minerals that does not cause magical cancellation.

sample

3
1 10
2 20
3 30

50