Kostya 是一名专门从事 Dota 2 学科的职业玩家。这款游戏的开发商 Valve Corporation 最近发布了一个新补丁,彻底颠覆了游戏的平衡。作为队长的科斯特亚意识到自己肩上的责任最大,所以他想从数学的角度对创新补丁进行分析,为自己的队伍在每场比赛中选择最好的英雄。
一场Dota 2比赛涉及两支队伍,每支队伍都必须选择本队选手将要效力的英雄,并且禁止多次选择同一个英雄,即使是在不同的队伍中也是如此。在Kostya团队要参加的大型电子竞技比赛中,比赛都是以队长模式进行的。在这种模式下,队长通过按照某种预先确定的顺序进行两种可能的行动之一来选择英雄:选择或禁止。
- 为团队挑选英雄。队长选择后,被选中的英雄会进入自己的队伍(稍后由一名队伍成员扮演),并且不能再被任何队伍选择。
- 禁止英雄。封禁后该英雄不会被派往任何队伍,但仍然无法再被任何队伍选择。
队长可能会错过选秀或禁赛。如果他错过了一次选秀,则会从当时可用的英雄中随机添加一个英雄到他的队伍中,如果他错过了一次禁令,则不会禁止任何英雄,就好像没有禁令一样。
Kostya 已经根据新的补丁修复确定了所有英雄的实力。当然,Kostya 知道选秀和禁用的顺序。一支球队的实力是球队英雄实力的总和,参加比赛的两支球队都力求最大化对自己有利的实力差异。帮助 Kostya 确定哪支球队(第一队或第二队)在比赛中具有优势,以及优势有多大。
输入
第一行包含一个整数 n (2 ≤ n ≤ 100) — Dota 2 中的英雄数量。
第二行包含 n 个整数 s1, s2, ..., sn (1 ≤ si ≤ 106) – 所有英雄的实力。
第三行包含一个整数 m (2 ≤ m ≤ min(n, 20)) — 队长必须执行的动作数量。
接下来的 m 行看起来像“action team”,其中 action 是所需的操作:选择(表示为“p”)或禁止(表示为“b”),而 team 是需要执行该操作的团队编号(编号 1 或 2)。
保证每支球队至少选秀一名。此外,每支球队的选秀次数和禁赛次数都是相同的。
输出
打印一个整数 - 如果两队队长都表现最佳,则第一队的实力与第二队的实力之间的差异。
示例
输入 #1
2 2 1 2 p 1 p 2
输出 #1
1
输入 #2
6 6 4 5 4 5 5 4 b 2 p 1 b 1 p 2
输出 #2
0
输入 #3
4 1 2 3 4 4 p 2 b 2 p 1 b 1
输出 #3
-2