Minimizing Cooking Time with Limited Overtaking

The school cafeteria has a unique way of serving meals. There are n students in a queue. Each student i is characterized by an integer flavor preference f_i and a tolerance B_i (a non‐negative integer). The cooking works as follows: the chef prepares one dish at a time. The time to cook a dish immediately after a dish with flavor a (for the previous student) when the current dish has flavor b is given by

where | and & denote the bitwise OR and AND operations respectively. Note that the first dish incur no cooking time. It can be verified that

i.e. the cooking time equals the number of bits which are different between a and b.

Normally the dishes would be served strictly following the initial queue order (students numbered 1 through n). However, to reduce the total cooking time the cafeteria is sometimes allowed to change the serving order. There is a catch though: each student i is only willing to tolerate at most the immediately following B_i students overtaking him. More formally, if in the final serving order a student originally at position i is overtaken by any student originally behind him, then every such student j must satisfy $$j-i\le B_i.$$

If any student finds that someone not among his immediately next B_i in the original order is served before him, he becomes extremely angry.

Your task is to determine the minimum total cooking time needed to cook dishes for all students, under a serving order that respects everyone’s tolerance.

inputFormat

The first line contains an integer n (the number of students).

Then follow n lines. The i-th of these lines contains two non‐negative integers f_i and B_i, where f_i represents the flavor preference and B_i represents the tolerance of the student originally at position i.

Note: The first dish prepared has no cooking time.

outputFormat

Output a single integer: the minimum total cooking time needed to serve all students while respecting the tolerance constraint.

sample

3
1 1
2 0
3 1

3