题目描述

最初有$N$种大小的橡皮泥。具体来说，对于每个$1≤i≤N$，有$C_i$个大小为$S_i$的橡皮泥。小高可以重复任意次数（可能为零）以任意顺序进行橡皮泥合成。
橡皮泥合成的过程如下：

• 选择两个相同大小的橡皮泥。假设这个大小为$X$，则会出现一个新的大小为$2X$的橡皮泥。然后，原来的两个橡皮泥消失。

小高想要最小化橡皮泥的数量。通过最优的合成序列，他最终能得到的最少橡皮泥数量是多少？

输入格式

输入从标准输入中以下列格式给出：
$N$
$S_1$ $C_1$
$S_2$ $C_2$
$\vdots$
$S_N$ $C_N$

输出格式

输出小高重复合成后可能得到的最少橡皮泥数量。

样例

3
3 3
5 1
6 1

3

3
1 1
2 1
3 1

3

1
1000000000 1000000000

13

样例解释

【样例1说明】
最初，有三个大小为$3$的橡皮泥，一个大小为$5$的橡皮泥，和一个大小为$6$的橡皮泥。
小高可以进行两次合成如下：

• 首先，选择两个大小为$3$的橡皮泥进行合成。此时将有一个大小为$3$的橡皮泥，一个大小为$5$的橡皮泥，和两个大小为$6$的橡皮泥。
• 接下来，选择两个大小为$6$的橡皮泥进行合成。此时将有一个大小为$3$的橡皮泥，一个大小为$5$的橡皮泥，和一个大小为$12$的橡皮泥。
  无论如何从初始状态重复合成，他都无法将橡皮泥数量减少到$2$个或更少，所以应该输出$3$。

【样例2说明】
他无法进行合成。

数据范围

$1 ≤ N ≤ 10^5$
$1 ≤ S_i,C_i ≤ 10^9$
$S_1, S_2, ..., S_N$ 都不相同
所有输入值都是整数

来源

• AtCoder ABC323D