CF377C.Captains Mode

Kostya is a progamer specializing in the discipline of Dota 2. Valve Corporation, the developer of this game, has recently released a new patch which turned the balance of the game upside down. Kostya, as the captain of the team, realizes that the greatest responsibility lies on him, so he wants to resort to the analysis of innovations patch from the mathematical point of view to choose the best heroes for his team in every game.

A Dota 2 match involves two teams, each of them must choose some heroes that the players of the team are going to play for, and it is forbidden to choose the same hero several times, even in different teams. In large electronic sports competitions where Kostya's team is going to participate, the matches are held in the Captains Mode. In this mode the captains select the heroes by making one of two possible actions in a certain, predetermined order: pick or ban.

• To pick a hero for the team. After the captain picks, the picked hero goes to his team (later one of a team members will play it) and can no longer be selected by any of the teams.
• To ban a hero. After the ban the hero is not sent to any of the teams, but it still can no longer be selected by any of the teams.

The team captain may miss a pick or a ban. If he misses a pick, a random hero is added to his team from those that were available at that moment, and if he misses a ban, no hero is banned, as if there was no ban.

Kostya has already identified the strength of all the heroes based on the new patch fixes. Of course, Kostya knows the order of picks and bans. The strength of a team is the sum of the strengths of the team's heroes and both teams that participate in the match seek to maximize the difference in strengths in their favor. Help Kostya determine what team, the first one or the second one, has advantage in the match, and how large the advantage is.

科斯佳是一名专注于《Dota 2》项目的电竞职业选手。该游戏的开发商 Valve 公司最近发布了一个新版本补丁，彻底颠覆了游戏的平衡性。作为战队队长，科斯佳深知自己肩负着最大责任，因此他希望从数学角度分析此次补丁更新，从而在每场比赛中为队伍选出最优的英雄阵容。

一场《Dota 2》比赛由两支队伍参与，每支队伍必须选择若干名英雄供本队选手使用；且同一英雄不可被重复选择，即使分属不同队伍亦不例外。在科斯佳所在战队即将参加的大型电子竞技赛事中，比赛采用“队长模式”（Captains Mode）。在此模式下，双方队长须依照既定顺序，轮流执行以下两种操作之一：选取（pick） 或 禁用（ban）。

• 选取（pick）一名英雄加入己方队伍：该英雄随即归属其所在队伍（之后将由该队某位选手使用），并从此不可再被任一队伍选中。
• 禁用（ban）一名英雄：该英雄不归属任何队伍，但仍从此不可被任一队伍选中。

队长可选择跳过一次选取或禁用操作。若跳过选取，则系统将从当前仍可选的英雄中随机挑选一名加入其队伍；若跳过禁用，则视为未执行禁用操作，即不禁止任何英雄。

科斯佳已根据本次补丁调整，评估出所有英雄的强度值。当然，他也知晓整场禁选流程中 picks 与 bans 的具体执行顺序。一支队伍的强度定义为其所拥有的全部英雄强度值之和；而比赛中双方队伍均以最大化己方相对于对方的强度差为目标。请帮助科斯佳判断：在该禁选规则下，先手方队伍还是后手方队伍更具优势？优势值为多少？

The first line contains a single integer n (2 ≤ n ≤ 100) — the number of heroes in Dota 2.

The second line contains n integers _s_1, _s_2, ..., s__n (1 ≤ s__i ≤ 106) — the strengths of all the heroes.

The third line contains a single integer m (2 ≤ m ≤ min(n, 20)) — the number of actions the captains of the team must perform.

Next m lines look like "action team", where action is the needed action: a pick (represented as a "p") or a ban (represented as a "b"), and team is the number of the team that needs to perform the action (number 1 or 2).

It is guaranteed that each team makes at least one pick. Besides, each team has the same number of picks and the same number of bans.

第一行包含一个整数 $n$（$2 \leq n \leq 100$）—— Dota 2 中英雄的数量。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \leq s_i \leq 10^6$）—— 所有英雄的强度值。

第三行包含一个整数 $m$（$2 \leq m \leq \min(n, 20)$）—— 队伍队长需要执行的操作次数。

接下来的 $m$ 行形如“action team”，其中 action 是所需执行的操作：选取（用 "p" 表示）或禁用（用 "b" 表示），而 team 是需要执行该操作的队伍编号（编号为 1 或 2）。

保证每支队伍至少进行一次选取。此外，每支队伍的选取次数相同，禁用次数也相同。

Print a single integer — the difference between the strength of the first team and the strength of the second team if the captains of both teams will act optimally well.

输出一个整数——即在双方队长均采取最优策略的情况下，第一支队伍的战力与第二支队伍的战力之差。