题目描述

题目译自 PA 2020 Runda 5 Programowanie współbieżne

为了准备算法竞赛，Bytie 决定学习一些并发编程的知识。毕竟，即使是 PA，也曾经出过分布式题（参考 PA 2018 Runda 4）。

Bytie 从编写 $n$ 个非常简单的程序开始。所有程序共享一个全局整数型变量 $x$，此外，每个程序都有一个私有的计数器 $y$。每个程序都由一连串的指令组成，每个指令都属于以下四种类型之一：

• $\texttt W$：将全局变量的值 $x$ 载入私有计数器 $y$。
• $\texttt Z$：将私有计数器 $y$ 的值写入全局变量 $x$。
• $\texttt{+ }c$：将 $y$ 的值加一正常数 $c$。
• $\texttt{- }c$：将 $y$ 的值减一正常数 $c$。

Bytie 并行运行所有的程序。所有计数器 $y$ 和变量 $x$ 的初始值都是 $0$。这些程序的指令交错执行，即所有程序的所有指令都是一个接一个地执行，对于每个时刻，每个程序满足它的指令的一个前缀以一定顺序被执行。

这种交错执行的方式结果是相当不幸的，变量 $x$ 的最终值是如此之小，以至于让 Bytie 非常惊讶。他甚至怀疑这是不可能的，是他的电脑骗了他。帮助 Bytie 验证他的疑惑，写一个验证器，对于给定的程序，计算所有程序并行执行后变量 $x$ 的最小可能值是多少。

输入格式

第一行一个整数 $t$，表示一组测试数据中测试点个数。

对于每个测试点，第一行一个整数 $n$，表示 Bytie 写的程序个数。

接下来 $2n$ 行描述每个程序。对于每个程序的描述有两行，第一行一个整数 $l$，表示程序中指令个数。第二行包含对这 $l$ 个指令的描述，指令是如下四种类型之一：

• 一个字符 $\texttt W$：表示载入指令；
• 一个字符 $\texttt Z$：表示写入指令；
• 一个字符 $\texttt{+}$ 和一个数字 $c$：表示给私有计数器加 $c$；
• 一个字符 $\texttt{-}$ 和一个数字 $c$：表示给私有计数器减 $c$。

对于一组数据中的所有测试点，$l$ 的总和不超过 $10^6$。

输出格式

输出 $t$ 行，第 $i$ 行是对第 $i$ 个测试点的回答，表示在并行执行这些程序后 $x$ 可能的最小值。

2
2
12
W + 2 Z W + 2 Z W + 2 Z W + 2 Z
12
W + 3 Z W + 3 Z W + 3 Z W + 3 Z
3
3
W W - 5
5
+ 9 Z + 1 Z W
8
+ 10 Z - 2 Z - 5 W - 1 Z

5
7

提示

样例 1 解释

对于第一个测试点，得到最小的 $x$ 程序指令执行顺序如下表。

数据范围

本题采用捆绑测试

对于 $100\%$ 的数据，保证 $1\le t\le 10^5$，$1\le n\le 10^5$，$1\le l\le 10^5$，$\sum{l}\leq 10^6$。