410719: GYM104090 H RPG Pro League

The International Computer Playing Company (ICPC) is recently scheduling the annual RPG Pro League (RPL). In the RPG game, there are three kinds of different roles: Damager, Synergier, and Buffer. A team consists of exactly four players. Only the following two types of teams are allowed in RPL:

• One Damager, two Synergiers, and one Buffer.
• Two Damagers, one Synergier, and one Buffer.

Before the real competition, the ICPC decides to hold an exhibition game. There are $$$n$$$ players, labeled by $$$1,2,\dots,n$$$. The $$$i$$$-th player can only play roles in set $$$S_i$$$, and the price to invite him to participate in the exhibition game is $$$p_i$$$ dollars.

You are working for the ICPC. Your job is to select which players to invite such that they can make the maximum number of valid teams, and the total cost is minimized. Note that a player can not join multiple teams.

Unfortunately, the players may always adjust their prices. You will be given $$$q$$$ events, in each event, the price of a player will be changed. Your task is to report the current minimum total cost for maximizing the valid teams after each event.

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), denoting the number of players.

Each of the following $$$n$$$ lines contains a string $$$S_i$$$ and an integer $$$p_i$$$ ($$$1\leq |S_i|\leq 3$$$, $$$1\leq p_i\leq 10^9$$$), denoting the role set and the price of the $$$i$$$-th player. $$$S_i$$$ consists of at most three different characters in $$$\{$$$'D', 'S', 'B'$$$\}$$$, denoting Damager, Synergier, and Buffer, respectively.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), denoting the number of events.

Each of the following $$$q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1\leq x_i\leq n$$$, $$$1\leq y_i\leq 10^9$$$), denoting the price of the $$$x_i$$$-th player is changed into $$$y_i$$$ dollars.

Output $$$q$$$ lines, the $$$i$$$-th ($$$1\leq i\leq q$$$) of which contains an integer denoting the minimum total cost for maximizing the valid teams after the $$$i$$$-th event.

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

10
12