史莱姆合成：最小化史莱姆数量 - 算法题

问题陈述

最初有N种大小的史莱姆。
/n具体而言，对于每个1/leq i/leq N，有C_i只大小为S_i的史莱姆。

高桥君可以按任意顺序重复任意次数的史莱姆合成（甚至可以是零次）。
/n史莱姆合成的操作如下：

/n
• 选择两只相同大小的史莱姆。选中的史莱姆大小为X，则会出现一只新的大小为2X的史莱姆。合成后，选中的原始史莱姆都会消失。
/n

高桥君希望尽量减少史莱姆的数量。/n在高桥君采取最佳合成序列后，他最终最少能剩下多少只史莱姆？

约束

/n
• 1/leq N/leq 10^5
/n
• 1/leq S_i/leq 10^9
/n
• 1/leq C_i/leq 10^9
/n
• S_1,S_2,/ldots,S_N各不相同。
/n
• 所有输入值均为整数。
/n

输入示例1

3/n3 3/n5 1/n6 1/n

输出示例1

3/n

最初，有3只大小为3的史莱姆，1只大小为5的史莱姆，1只大小为6的史莱姆。
/n高桥君可以按以下方式进行2次合成：

/n
• 首先，选择2只大小为3的史莱姆进行合成。会得到1只大小为3的史莱姆，1只大小为5的史莱姆，2只大小为6的史莱姆。
/n
• 然后，选择2只大小为6的史莱姆进行合成。会得到1只大小为3的史莱姆，1只大小为5的史莱姆，1只大小为12的史莱姆。
/n

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

输入示例2

3/n1 1/n2 1/n3 1/n

输出示例2

3/n

他无法进行合成。

输入示例3

1/n1000000000 1000000000/n

输出示例3

13/n