AT_abc323_d [ABC323D] Merge Slimes

题目描述

最初，有 $N$ 种不同尺寸的史莱姆。
具体来说，对于 $1\leq i\leq N$，有 $C_i$ 只尺寸为 $S_i$ 的史莱姆。

高桥君可以按照任意顺序、任意次数（可以为 $0$ 次）重复进行史莱姆的合成操作。
每次史莱姆的合成操作如下：

• 选择两只相同尺寸的史莱姆。如果被选中的史莱姆尺寸为 $X$，则会生成一只尺寸为 $2X$ 的新史莱姆。合成后，被选中的两只原史莱姆都会消失。

高桥君希望使史莱姆的总数最少。请问高桥君通过合理地重复合成操作后，最少能剩下多少只史莱姆？

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$ $C_1$
$S_2$ $C_2$
$\vdots$
$S_N$ $C_N$

输出格式

请输出高桥君通过合成操作后可能剩下的最小史莱姆数量。

输入输出样例 #1

输入 #1

3
3 3
5 1
6 1

输出 #1

3

输入输出样例 #2

输入 #2

3
1 1
2 1
3 1

输出 #2

3

输入输出样例 #3

输入 #3

1
1000000000 1000000000

输出 #3

13

说明/提示

限制条件

• $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$ 互不相同。
• 输入均为整数。

样例解释 1

最初，尺寸为 $3$ 的史莱姆有 $3$ 只，尺寸为 $5$ 的史莱姆有 $1$ 只，尺寸为 $6$ 的史莱姆有 $1$ 只。高桥君可以进行如下两次合成操作：

• 首先，选择两只尺寸为 $3$ 的史莱姆进行合成。此时，尺寸为 $3$ 的史莱姆剩 $1$ 只，尺寸为 $5$ 的史莱姆 $1$ 只，尺寸为 $6$ 的史莱姆 $2$ 只。
• 接着，选择两只尺寸为 $6$ 的史莱姆进行合成。此时，尺寸为 $3$ 的史莱姆 $1$ 只，尺寸为 $5$ 的史莱姆 $1$ 只，尺寸为 $12$ 的史莱姆 $1$ 只。

无论高桥君如何合成，都无法将史莱姆数量减少到 $2$ 只以下，因此输出 $3$。

样例解释 2

高桥君无法进行任何合成操作。

由 ChatGPT 4.1 翻译