合并史莱姆

题目描述

初始时有 $N$ 种大小的史莱姆。

具体地，对于每个 $1\leq i\leq N$，有 $C_i$ 只大小为 $S_i$ 的史莱姆。

高桥君可以以任意顺序、任意次数（可以为 0 次）重复进行史莱姆合成。

史莱姆合成的操作如下：

选择两只大小相同的史莱姆。设其大小为 $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 只大小为 $3$ 的史莱姆、1 只大小为 $5$ 的史莱姆和 1 只大小为 $6$ 的史莱姆。

高桥君可以按如下方式合成两次：

首先，选择两只大小为 $3$ 的史莱姆进行合成。此时会有 1 只大小为 $3$、1 只大小为 $5$ 和 2 只大小为 $6$ 的史莱姆。

接下来，选择两只大小为 $6$ 的史莱姆进行合成。此时会有 1 只大小为 $3$、1 只大小为 $5$ 和 1 只大小为 $12$ 的史莱姆。

无论从初始状态如何合成，都无法将数量减少到 2 只或更少，因此应输出 $3$。

3
1 1
2 1
3 1

3

无法进行合成。

1
1000000000 1000000000

13

数据范围

• $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$ 各不相同。
• 输入中的所有数值均为整数。