CF1070F Debate

伯兰德即将举行选举，只有两位候选人——Alice 和 Bob。 伯兰德的主流电视台计划举办一场政治辩论。有 $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 \times 10^5$），表示希望作为观众参与辩论的人数。 接下来的 $n$ 行，每行描述一个人，包含一个字符串 $s_i$ 和一个整数 $a_i$，用空格分隔（$1 \le a_i \le 5000$），其中 $s_i$ 表示该人的政治立场（可能的取值为 "00"、"10"、"01"、"11"），$a_i$ 表示第 $i$ 个人的影响力。

输出一个整数，表示满足条件的观众集合的最大总影响力。如果无法满足条件，则输出 $0$。

在第一个样例中，可以邀请 $4$ 位观众以最大化总影响力：第 $1$、$2$、$3$ 和 $6$ 位。他们的政治立场分别为 "11"、"10"、"01" 和 "00"。因此，总共 $4$ 人中有 $2$ 人支持 Alice，有 $2$ 人支持 Bob。总影响力为 $6+4+3+9=22$。 在第二个样例中，可以选择除第 $5$ 个人以外的所有人。 在第三个样例中，可以选择第 $1$、$4$、$5$ 和 $6$ 个人。 在第四个样例中，无法选择任何非空观众集合。 由 ChatGPT 4.1 翻译