← 返回题目列表

Codeforces · 1070/F

F. 辩论

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

伯兰的选举即将到来。只有两个候选人——爱丽丝和鲍勃。

Berland 主要电视频道计划播放政治辩论。有$$$n$$$ 人想作为旁观者参加辩论。每个人都通过他们的影响力和政治观点来描述。政治观点有四种:

- 不支持任何候选人(此类表示为“00”),
- 支持Alice但不支持Bob(这种表示为“10”),
- 支持Bob但不支持Alice(这种表示为“01”),
- 支持两位候选人(这种表示为“11”)。

电视频道的方向想邀请其中一些人参加辩论。受邀观众的名单应满足三个条件:

- 至少一半观众支持 Alice(即 $$$2 \cdot a \ge m$$$,其中 $$$a$$$ 是支持 Alice 的观众数量,$$$m$$$ 是观众总数),
- 至少一半观众支持 Bob(即 $$$2 \cdot b \ge m$$$,其中 $$$b$$$ 是支持 Bob 的观众数量,$$$m$$$ 是观众总数),
- 观众的总影响力是最大可能的。

帮助电视频道方向选择这样的非空观众集,或者告诉这是不可能的。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$) — 想要作为旁观者参加辩论的人数。

这些人将在接下来的 $$$n$$$ 行中进行描述。每行描述一个人,包含字符串 $$$s_i$$$ 和整数 $$$a_i$$$,以空格分隔 ($$$1 \le a_i \le 5000$$$),其中 $$$s_i$$$ 表示个人的政治观点(可能的值 — “00”、“10”、“01”、“11”),而 $$$a_i$$$ — 该人的影响力第 $$$i$$$ 人。

输出

打印一个整数 - 一组观众的最大可能总影响力,以便至少一半人支持 Alice,至少一半人支持 Bob。如果不可能,则打印 0。

示例

输入 #1

6
11 6
10 4
01 3
00 3
00 7
00 9

输出 #1

22

输入 #2

5
11 1
01 1
00 100
10 1
01 1

输出 #2

103

输入 #3

6
11 19
10 22
00 18
00 29
11 29
10 28

输出 #3

105

输入#4

3
00 5000
00 5000
00 5000

输出#4

0

注意

在第一个示例中,可以邀请 $$$4$$$ 观众来最大化总影响力:$$$1$$$、$$$2$$$、$$$3$$$ 和 $$$6$$$。他们的政治观点是:“11”、“10”、“01”和“00”。因此,$$$4$$$ 观众中总计 $$$2$$$ 支持 Alice,$$$4$$$ 观众中 $$$2$$$ 支持 Bob。总影响力为$$$6+4+3+9=22$$$。

在第二个示例中,方向可以选择除第 $$$5$$$ 人之外的所有人。

在第三个示例中,方向可以选择具有索引的人:$$$1$$$、$$$4$$$、$$$5$$$ 和 $$$6$$$。

在第四个示例中,不可能选择任何非空观众集。