题目描述

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

橡皮泥合成的过程如下：

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

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

输入格式

输入从标准输入中以下列格式给出：

$N$

$S_1$ $C_1$

$S_2$ $C_2$

$\vdots$

$S_N$ $C_N$

输出格式

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

输入输出样例 #1

输入 #1

3
3 3
5 1
6 1

输出 #1

3

输入输出样例 #2

输入 #2

3
1 1
2 1
3 1

输出 #2

3

输入输出样例 #3

输入 #3

1
1000000000 1000000000

输出 #3

13

说明/提示

样例说明 1

最初，有三个大小为 $3$ 的橡皮泥，一个大小为 $5$ 的橡皮泥，和一个大小为 $6$ 的橡皮泥。

小高可以进行两次合成如下：

• 首先，选择两个大小为 $3$ 的橡皮泥进行合成。此时将有一个大小为 $3$ 的橡皮泥，一个大小为 $5$ 的橡皮泥，和两个大小为 $6$ 的橡皮泥。
• 接下来，选择两个大小为 $6$ 的橡皮泥进行合成。此时将有一个大小为 $3$ 的橡皮泥，一个大小为 $5$ 的橡皮泥，和一个大小为 $12$ 的橡皮泥。

无论如何从初始状态重复合成，他都无法将橡皮泥数量减少到 $2$ 个或更少，所以应该输出 $3$。

样例说明 2

他无法进行合成。

数据范围

• $1\leq\ N\leq\ 10^5$
• $1\leq\ S_i\leq\ 10^9$
• $1\leq\ C_i\leq\ 10^9$
• $S_1,S_2,\ldots,S_N$ 都不相同。
• 所有输入值都是整数