4204: Merge Slimes

# Merge Slimes ### 内存 1024MB ### 时间 2S ## 题目描述 最初有$N$种大小的橡皮泥。具体来说，对于每个$1≤i≤N$，有$C_i$个大小为$S_i$的橡皮泥。小高可以重复任意次数（可能为零）以任意顺序进行橡皮泥合成。 橡皮泥合成的过程如下： - 选择两个相同大小的橡皮泥。假设这个大小为$X$，则会出现一个新的大小为$2X$的橡皮泥。然后，原来的两个橡皮泥消失。 小高想要最小化橡皮泥的数量。通过最优的合成序列，他最终能得到的最少橡皮泥数量是多少？ ## 输入格式 输入从标准输入中以下列格式给出： $N$ $S_1$ $C_1$ $S_2$ $C_2$ $\vdots$ $S_N$ $C_N$ ## 输出格式 输出小高重复合成后可能得到的最少橡皮泥数量。 ## 输入输出样例 ### 输入样例1 ``` 3 3 3 5 1 6 1 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 3 1 1 2 1 3 1 ``` ### 输出样例2 ``` 3 ``` ### 输入样例3 ``` 1 1000000000 1000000000 ``` ### 输出样例3 ``` 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$ 都不相同 所有输入值都是整数 ## 题目来源 ABC323D