Repaint the ball#8773
Sem and Yura have balls, each either black or white. Each ball has a value c_i and can be repainted a maximum of a_i times.
They decide to play a game where, in each turn, a player can repaint a ball to either black or white, or choose to skip their turn. A ball cannot be repainted more than a_i times, and it can be repainted in the same color it already is. Sem goes first. The game concludes when no ball can be repainted further or both players skip their turns consecutively.
After the game, Sem collects all the white balls, and Yura takes all the black ones. Each player's score is the sum of the values of their respective balls. Both players aim to maximize their scores. Determine the final scores for both players if they play optimally.
The first line contains a single integer (1 \leq n \leq 10^5) — the number of balls.
The second line contains integers c_1, c_2, \ldots, c_n (1 \leq c_i \leq 10^9) — the value of the -th ball.
The third line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the maximum number of times the -th ball can be repainted.
The fourth line contains characters W and B. The -th character is W if the -th ball is initially white, and B if it is black.
Output two integers — the scores of Sem and Yura, respectively.
Example 1