← 返回题目列表

AtCoder · abc323_d

G. 合并史莱姆

中文机器翻译题面 查看原题

分数: 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