Migrated from Lutece 1354 柱爷很忙

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

柱爷很忙。

柱爷每天不仅要炒股，还要策划和实施抢银行，同时还要水群、回答IOI小朋友们问题，又或者要练习咸鱼神功。

为了能更快完成这些事，把时间拿来玩BattleBlock Theater，柱爷把要做的$N$件事的类型$a_i$按原本做的顺序记录下来，计算最少要花费的时间。

万事冥冥之中俱有关联。假如柱爷做事$i$的前一件事是事$j$，所花费的时间为$(a_i |a_j)-(a_i\&a_j)$，其中$|,\&$是位运算符。若柱爷做事$i$前没有做事，则柱爷要花费的时间为$a_i$。

但事情总有轻重缓急之分，按原本顺序的事$i$最多能推迟到做完任意件紧接着事$i$之后的事$j，i< j\leq i+b_i$后做，即原本顺序的事$k,k>i+b_i$不能在事$i$之前完成。

柱爷已经知道自己最少要花多少时间了，请问你知道吗。

Input

第一行一个数$N$，代表柱爷要做$N$件事。$1\leq N\leq 1000$

之后$N$行，每行两个数$a_i，b_i$，代表事情的类型和重要程度。$1\leq a_i\leq 1000，0\leq b_i\leq 7$

Output

输出一行一个数，即柱爷最少要花的时间。

Samples

2
5 0
4 0

6

2
5 1
4 0

5

Note

对于样例2，柱爷可以先做事2再做事1，答案为$4+(4|5)-(4\&5)=5$

Resources

2016 UESTC Training for Dynamic Programming