CF1070F.Debate

Elections in Berland are coming. There are only two candidates — Alice and Bob.

The main Berland TV channel plans to show political debates. There are $n$ people who want to take part in the debate as a spectator. Each person is described by their influence and political views. There are four kinds of political views:

• supporting none of candidates (this kind is denoted as "00"),
• supporting Alice but not Bob (this kind is denoted as "10"),
• supporting Bob but not Alice (this kind is denoted as "01"),
• supporting both candidates (this kind is denoted as "11").

The direction of the TV channel wants to invite some of these people to the debate. The set of invited spectators should satisfy three conditions:

• at least half of spectators support Alice (i.e. $2 \cdot a \ge m$, where $a$ is number of spectators supporting Alice and $m$ is the total number of spectators),
• at least half of spectators support Bob (i.e. $2 \cdot b \ge m$, where $b$ is number of spectators supporting Bob and $m$ is the total number of spectators),
• the total influence of spectators is maximal possible.

Help the TV channel direction to select such non-empty set of spectators, or tell that this is impossible.

伯兰德的选举即将来临。目前只有两位候选人：爱丽丝（Alice）和鲍勃（Bob）。

伯兰德主流电视台计划播出政治辩论节目。共有 $n$ 人希望作为观众参加此次辩论。每个人由其影响力和政治立场描述。政治立场共分为四类：

• 不支持任何一位候选人（记为 “00”），
• 仅支持爱丽丝、不支持鲍勃（记为 “10”），
• 仅支持鲍勃、不支持爱丽丝（记为 “01”），
• 同时支持两位候选人（记为 “11”）。

电视台导演希望邀请其中一部分人作为观众出席辩论。被邀请的观众集合需满足以下三个条件：

• 至少一半的观众支持爱丽丝（即 $2 \cdot a \ge m$，其中 $a$ 表示支持爱丽丝的观众人数，$m$ 表示观众总人数），
• 至少一半的观众支持鲍勃（即 $2 \cdot b \ge m$，其中 $b$ 表示支持鲍勃的观众人数，$m$ 表示观众总人数），
• 观众的总影响力尽可能大。

请帮助电视台导演选出一个满足上述条件的非空观众集合；若不存在这样的集合，请说明这是不可能的。

The first line contains integer $n$ ($1 \le n \le 4\cdot10^5$) — the number of people who want to take part in the debate as a spectator.

These people are described on the next $n$ lines. Each line describes a single person and contains the string $s_i$ and integer $a_i$ separated by space ($1 \le a_i \le 5000$), where $s_i$ denotes person's political views (possible values — "00", "10", "01", "11") and $a_i$ — the influence of the $i$-th person.

第一行包含一个整数 $n$（$1 \le n \le 4\cdot10^5$）—— 表示希望作为观众参加辩论的人数。

接下来的 $n$ 行描述了这 $n$ 个人。每行描述一个人，包含一个字符串 $s_i$ 和一个整数 $a_i$，二者以空格分隔（$1 \le a_i \le 5000$），其中 $s_i$ 表示该人的政治立场（可能取值为 "00"、"10"、"01"、"11"），$a_i$ 表示第 $i$ 个人的影响力。

Print a single integer — maximal possible total influence of a set of spectators so that at least half of them support Alice and at least half of them support Bob. If it is impossible print 0 instead.

输出一个整数——满足“至少一半观众支持 Alice 且至少一半观众支持 Bob”的观众集合所能达到的最大总影响力。若无法满足条件，则输出 0。

In the first example $4$ spectators can be invited to maximize total influence: $1$, $2$, $3$ and $6$. Their political views are: "11", "10", "01" and "00". So in total $2$ out of $4$ spectators support Alice and $2$ out of $4$ spectators support Bob. The total influence is $6+4+3+9=22$.

In the second example the direction can select all the people except the $5$-th person.

In the third example the direction can select people with indices: $1$, $4$, $5$ and $6$.

In the fourth example it is impossible to select any non-empty set of spectators.

在第一个例子中，最多可以邀请 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$ 的观众。

在第四个例子中，无法选择任何非空的观众集合。