题目描述

有 $n$ 种不同尺寸的原材料，第 $i$ 个原材料的尺寸为 $s_i$，数量为 $c_i$。

可以选择两个相同尺寸为 $X$ 的原材料进行合并，合成一个新的大小为 $2 \times X$ 的原材料。这一操作可以执行任意多次，问能得到的最少的原材料数量是多少？

输入格式

第一行一个整数 $n$

记下来有 $n$ 行，每行两个整数 $s_i$ 和 $c_i$。

数据范围

$1 \le n \le 10^5$

$1 \le s_i \le 10^9$

$1 \le c_i \le 10^9$

输出格式

一个整数，代表最终能得到最少原材料个数。

样例

3
3 3
5 1
6 1

3

3
1 1
2 1
3 1

3

1
1000000000 1000000000

13