分数: 425 点
问题陈述
最初,有 N 史莱姆的尺寸。
具体来说,对于每个 1\leq i\leq N,有 C_i 史莱姆大小 S_i.
高桥可以以任何顺序重复史莱姆合成任意次数(可能为零)。
粘液合成如下进行。
- 选择两个史莱姆 相同 尺寸。设这个尺寸为 X,以及一个新尺寸的史莱姆 出现 2X 。然后,原来的两条史莱姆就消失了。
高桥想要尽量减少史莱姆的数量。 通过最佳合成顺序,他最终能得到的史莱姆最少数量是多少?
约束
- 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 都是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N S_1 C_1 S_2 C_2 \vdots S_N C_N
输出
在高桥重复合成后打印尽可能少的史莱姆数。
示例输入 1
3 3 3 5 1 6 1
示例输出 1
3
最初,有三种大小的史莱姆 3,尺寸之一 5,以及尺寸之一 6.
Takahashi 可以执行两次合成,如下所示:
- 首先,选择两个大小相同的史莱姆进行合成 3。将会有一个大小的史莱姆 3,尺寸之一 5,以及两个尺寸 6.
- 接下来,选择两个大小相同的史莱姆进行合成 6。将会有一个大小的史莱姆 3,尺寸之一 5,以及尺寸之一 12.
无论他如何从初始状态重复合成,他都无法将史莱姆的数量减少到 2 或更少,所以你应该打印 3.
示例输入 2
3 1 1 2 1 3 1
示例输出 2
3
他无法进行合成。
示例输入 3
1 1000000000 1000000000
示例输出 3
13