Monsters Battle

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME81/hindi/MONSTBAT.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME81/bengali/MONSTBAT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME81/mandarin/MONSTBAT.pdf), [Russian](http://www.codechef.com/download/translated/LTIME81/russian/MONSTBAT.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME81/vietnamese/MONSTBAT.pdf) as well. Chef and Chefina are playing a game. Chef has $N$ monsters (numbered $1$ through $N$). For each valid $i$, the $i$th monster has a value $V_{1,i}$ and it is either in attack mode or defense mode. The initial states of the monsters are described by a string $D_1$: for each valid $i$, the $i$th monster is in attack mode if the $i$th character of $D_1$ is 'A' or in defense mode if the $i$th character is 'D'. Chefina has $M$ monsters (numbered $1$ through $M$). Their values are $V_{2,1}, V_{2,2}, \ldots, V_{2,M}$ and their initial states are described by a string $D_2$ in the same way. In the game, the players alternate turns; Chef plays first. During each turn, the current player may either end the game immediately or do the following: choose one of their own living monsters in attack mode, choose a monster of the other player in defense mode, attack and kill this defending monster and change the attacking monster to defense mode. Note that once a monster is in defense mode, it never changes to attack mode. Each player is trying to maximise the difference $XY$, where $X$ is the sum of values of this player's living monsters (in both modes, but only if they are alive) and $Y$ is the sum of values of the opponent's living monsters. Assuming that both players are playing optimally, calculate the sum of values of Chef's living monsters minus the sum of values of Chefina's living monsters after the game ends. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  The second line contains $N$ spaceseparated integers $V_{1,1}, V_{1,2}, \ldots, V_{1,N}$.  The third line contains a single string $D_1$ with length $N$.  The fourth line contains $M$ spaceseparated integers $V_{2,1}, V_{2,2}, \ldots, V_{2,M}$.  The fifth line contains a single string $D_2$ with length $M$. ### Output For each test case, print a single line containing one integer ― the sum of values of Chef's living monsters minus the sum of values of Chefina's living monsters after the game ends. ### Constraints  $1 \le T \le 100$  $1 \le N, M \le 10^5$  initially, Chefina has at least one monster in defense mode  $D_1$ and $D_2$ contain only characters 'A' and 'D'  $1 \le V_{i,j} \le 10^9$ for each valid $i, j$  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $M$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):**  $N, M \le 10^3$  initially, Chefina has exactly one monster in defense mode and Chef has no monsters in defense mode  the sum of $N$ over all test cases does not exceed $10^4$  the sum of $M$ over all test cases does not exceed $10^4$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 3 3 5 4 60 AAA 2 15 16 DAA ``` ### Example Output ``` 38 ``` ### Explanation **Example case 1:** Chef attacks Chefina's first monster with his second monster. On the next turn, Chefina decides to end the game.Author:  admin3 
Editorial  https://discuss.codechef.com/problems/MONSTBAT 
Tags  admin3, easymedium, gametheory, ltime81, recursion, tmwilliamlin 
Date Added:  28022020 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 