伯兰的选举即将到来。只有两个候选人——爱丽丝和鲍勃。
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$$$。
在第四个示例中,不可能选择任何非空观众集。