问题描述

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

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

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

计算所有程序并行执行后变量 $x$ 的最小可能值是多少。

输入格式

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

每组数据第一行一个整数 $n$，表示程序的数量。每组数据的第 $2$ 到 $2n+1$ 行，每两行表示一个程序。

每个程序的第一行一个整数 $l_i$，表示该程序的指令数量。每个程序的第二行是 $l_i$ 个空格分隔的指令，每个指令的格式是如下四种之一：

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

输出格式

每组数据输出一行一个整数，表示答案。

输入样例1

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

输出样例1

5
7

样例 1 解释

对于第一组数据，得到最小的 $x$ 程序指令执行顺序如下表。

该样例满足子任务的约束。

数据约束

• $1\le t\le 10^6$
• $1\le n\le 10^6$
• $1\le l_i\le 10^6$
• $1\le c_{ij}\le 10^9$
• 一个测试点中的所有数据的 $\sum l_i$ 之和不超过 $10^6$

子任务的列表如下：