Harry Potter and the Polyjuice Potion

Polyjuice potion is one of the most famous magic medicines in Harry Porter which had been made by our talented witch Hermione Jean Granger when she was a little girl. But at the very beginning, she didn't know the prescription, so she had to try several materials to make it up. After that, she found there were only twenty materials which could possibly make the polyjuice potion. And she also noticed that some combination of the materials of the twenty materials will get an effect Ei(-1000 < Ei < 1000).If she choose a subset S of the materials, the final effect will be the sum of effect values of all combinations appeared in S. Because Hermione is very clever, she calculated all the effect value of the combinations. So what's the maximum effect value the polyjuice potion will get?

Input contains multiple test cases(at most 10).
For each test case, the first line contains a positive integer N(N <= 100000) indicate the number of the combinations.
Then N lines follow, each line contains two number c (0 <= c < 2^20), v(-1000 < v < 1000),indicate the effect value of the combination c (binary representation).
Input ends with a negtive number.

For each test case output a number indicates the maximum value of the polyjuice potion.

3
1 9
2 -10
3 300
-1

299

fatboy_cw@WHU

2011 Multi-University Training Contest 15 - Host by WHU