P9106 [PA 2020] Concurrent Programming

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 5 [Programowanie współbieżne](https://sio2.mimuw.edu.pl/c/pa-2020-1/pro/).** To prepare for algorithmic contests, Bytie decided to learn some knowledge about concurrent programming. After all, even in PA there have been distributed problems before (see PA 2018 Round 4). Bytie starts by writing $n$ very simple programs. All programs share a global integer variable $x$. In addition, each program has a private counter $y$. Each program consists of a sequence of instructions, and each instruction is one of the following four types: - $\texttt W$: load the value of the global variable $x$ into the private counter $y$. - $\texttt Z$: write the value of the private counter $y$ into the global variable $x$. - $\texttt{+ }c$: increase $y$ by a positive constant $c$. - $\texttt{- }c$: decrease $y$ by a positive constant $c$. Bytie runs all programs in parallel. The initial values of all counters $y$ and the variable $x$ are $0$. The instructions of these programs are executed in an **interleaved** way: all instructions of all programs are executed one by one, and at any moment, for each program, some prefix of its instructions has been executed, and the overall execution order is some interleaving of these prefixes. This interleaving execution leads to a rather unfortunate result: the final value of $x$ can be so small that Bytie is very surprised. He even suspects this is impossible, and that his computer is cheating him. Help Bytie verify this by writing a checker: for the given programs, compute the minimum possible final value of $x$ after all programs run in parallel.

The first line contains an integer $t$, the number of test cases. For each test case, the first line contains an integer $n$, the number of programs written by Bytie. The next $2n$ lines describe the programs. Each program is described by two lines: the first line contains an integer $l$, the number of instructions in the program. The second line contains the descriptions of these $l$ instructions. Each instruction is one of the following four types: - a character $\texttt W$: a load instruction. - a character $\texttt Z$: a write instruction. - a character $\texttt{+}$ and a number $c$: add $c$ to the private counter. - a character $\texttt{-}$ and a number $c$: subtract $c$ from the private counter. Over all test cases, the sum of $l$ does not exceed $10^6$.

Output $t$ lines. The $i$-th line is the answer for the $i$-th test case, meaning the minimum possible value of $x$ after running these programs in parallel.

#### Explanation for Sample 1 For the first test case, the following table shows an execution order of the program instructions that achieves the minimum $x$.  ------------ #### Constraints **This problem uses bundled testdata.** For $100\%$ of the data, it is guaranteed that $1\le t\le 10^5$, $1\le n\le 10^5$, $1\le l\le 10^5$, $\sum{l}\leq 10^6$. Translated by ChatGPT 5