国际计算机游戏公司（ICPC）最近正在筹划年度 RPG 职业联赛（RPL）。在 RPG 游戏中，有三种不同的角色：输出（Damager）、辅助（Synergier）和增益（Buffer）。一个队伍恰好由四名玩家组成。在 RPL 中，只允许以下两种类型的队伍：

• 一名输出、两名辅助和一名增益。
• 两名输出、一名辅助和一名增益。

在正式比赛前，ICPC 决定举办一场表演赛。共有 $n$ 名玩家，编号为 $1, 2, \dots, n$。第 $i$ 名玩家只能担任集合 $S_i$ 中的角色，邀请他参加表演赛的价格为 $p_i$ 美元。

你正在为 ICPC 工作。你的任务是选择邀请哪些玩家，使得他们能组成的有效队伍数量最多，且总成本最小。注意，一名玩家不能加入多个队伍。

不幸的是，玩家可能会随时调整他们的价格。你将收到 $q$ 个事件，在每个事件中，一名玩家的价格会发生变化。你的任务是在每次事件后，报告在最大化有效队伍数量的前提下的当前最小总成本。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示玩家数量。

接下来的 $n$ 行，每行包含一个字符串 $S_i$ 和一个整数 $p_i$ ($1 \le |S_i| \le 3, 1 \le p_i \le 10^9$)，表示第 $i$ 名玩家的角色集合和价格。$S_i$ 由 {'D', 'S', 'B'} 中的至多三个不同字符组成，分别代表输出（Damager）、辅助（Synergier）和增益（Buffer）。

下一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示事件数量。

接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le n, 1 \le y_i \le 10^9$)，表示第 $x_i$ 名玩家的价格变更为 $y_i$ 美元。

输出格式

输出 $q$ 行，第 $i$ 行 ($1 \le i \le q$) 包含一个整数，表示在第 $i$ 次事件后，最大化有效队伍数量时的最小总成本。

样例

样例输入 1

5
BS 3
D 3
B 2
D 4
D 5
2
5 2
1 5

样例输出 1

10
12