传统题 2000ms 512MiB

合成

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

存在 nn 种物品,第 ii 种的体积为 aia_i,数量有 bib_i

一旦有 2k2^k 个物品的体积均为 vv,则将它们合成为一个体积为 2k×v2^k\times v 的物品

容易知道,无论用何种方式合并,最终所剩物品数量是确定的

求最后剩下多少个物品

输入格式

输入共 n+1n+1

第一行一个整数 nn,表示物品的种类数量

接下来 nn 行,每行两个整数 ai,bia_i,b_i 表示此种物品的体积和数量

输出格式

一行一个整数,表示最终所剩的物品数量

样例数据

样例一

input

1
114 514

output

2

样例二

input

5
17 6
1 10
8 16
14 3
18 20

output

9

样例三

input

20
47 62239
62 35348
1 47917
67 77046
42 56555
54 52866
41 26781
21 94012
85 2905
64 40748
36 90411
46 79203
99 35494
55 73787
40 73599
71 27203
60 71267
74 38458
2 72838
45 93570

output

144

数据范围与约定

对于 10%10\% 的数据,n=1n=1

对于 40%40\% 的数据,n500n\le 500

对于 100%100\% 的数据,1n1051\le n \le 10^51ai,bi1091\le a_i, b_i\le 10^9,保证 aia_i 两两不相同

[YDRB#002] 一步步脚踏实地 · 云斗九月 Bronze Round

未参加
状态
已结束
规则
IOI(严格)
题目
5
开始于
2024-9-8 9:00
结束于
2024-9-8 20:00
持续时间
4 小时
主持人
参赛人数
126