P4570 [BJWC2011] Elements

It is said that in ancient times, on the western continent, Magic Land, people had already mastered the technique of forging staffs from magic ores. People then realized that the power of a staff depended on the ores used. In general, the more ores used, the stronger the power; but too much of anything backfires: sometimes people used many ores in pursuit of greater power, only to find during forging that all the magic ores disappeared, making it impossible to forge a staff. This phenomenon is called "magic cancellation." In particular, if more than one ore of the same type is used during forging, "magic cancellation" will certainly occur. Later, as understanding improved, this phenomenon was well explained. After many experiments, the renowned mage Dmitri discovered: if we assign a reasonable numbering to each currently known ore type (the numbers are positive integers, called the element index of the ore), then a multiset of ores will produce "magic cancellation" if and only if there exists a non-empty subset whose element indices XOR to zero (if you are not familiar with XOR, please see the glossary on the next page). For example, using two identical ores will definitely cause "magic cancellation," because the element indices of these two ores are the same and XOR to zero. Moreover, people found an effective way to measure magic power, and it is known that the magic power of the synthesized staff equals the sum of the magic power of each ore used. The magic power values of all currently known ores have been measured, and the element index of each ore has been inferred through experiments. Now, given the above information about the ores, please compute the maximum possible magic power of a staff that could be forged.

The first line contains a positive integer $N$, representing the number of ore types. The next $N$ lines each contain two positive integers $\mathrm{Number}_i$ and $\mathrm{Magic}_i$, representing the element index and magic power value of this ore type.

Output a single line with one integer representing the maximum magic power.

### Sample Explanation Due to the fact of "magic cancellation," at most one ore of each type can be used. If all three types of ores are used, since their element indices XOR to $1\ \mathrm{xor}\ 2\ \mathrm{xor}\ 3 = 0$, magic cancellation will occur and no staff can be obtained. It can be seen that the optimal plan is to choose the last two types of ores, with magic power $20+30=50$. ### Constraints For all testdata: $1 \leq N \leq 1000$, $1 \leq \mathrm{Number}_i \le 10^{18}$, $1 \leq \mathrm{Magic}_i \le 10^4$. Translated by ChatGPT 5