题目描述

存在 $n$ 种物品，第 $i$ 种的体积为 $a_i$，数量有 $b_i$ 个

一旦有 $2^k$ 个物品的体积均为 $v$，则将它们合成为一个体积为 $2^k\times v$ 的物品

容易知道，无论用何种方式合并，最终所剩物品数量是确定的

求最后剩下多少个物品

输入格式

输入共 $n+1$ 行

第一行一个整数 $n$，表示物品的种类数量

接下来 $n$ 行，每行两个整数 $a_i,b_i$ 表示此种物品的体积和数量

输出格式

一行一个整数，表示最终所剩的物品数量

样例数据

样例一

input

1
114 514

output

2

样例二

input

5
17 6
1 10
8 16
14 3
18 20

output

9

样例三

input

20
47 62239
62 35348
1 47917
67 77046
42 56555
54 52866
41 26781
21 94012
85 2905
64 40748
36 90411
46 79203
99 35494
55 73787
40 73599
71 27203
60 71267
74 38458
2 72838
45 93570

output

144

数据范围与约定

对于 $10\%$ 的数据，$n=1$

对于 $40\%$ 的数据，$n\le 500$

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le a_i, b_i\le 10^9$，保证 $a_i$ 两两不相同