Concurrent Programs: Minimizing the Global Variable

In this problem, you are given n programs that execute concurrently. All programs share a global integer variable x (initially 0) and each program has its own private counter y (initially 0). Each program consists of a sequence of instructions. There are four types of instructions:

• W: Load the current global variable x into the private counter y.
• Z: Write the value of the private counter y into the global variable x.
• + c: Increase the private counter y by a positive integer constant c.
• - c: Decrease the private counter y by a positive integer constant c.

The instructions of all programs are interleaved in an arbitrary way while preserving the order of instructions within each program. Your task is to determine the minimum possible final value of the global variable x after all instructions of all programs have been executed.

Note: Because of the interleaving, the order in which Z instructions (which update x) are executed can affect the final outcome. For instructions that begin with a W, the effect is affine: if W appears, it loads the current (and possibly very low) value of x into y, which is then modified by subsequent + and - operations before a Z writes it back to x.

All programs and their instructions must be executed completely. You can choose any valid interleaving (subject to preserving the order inside each program) so as to minimize the final value of x.

It is guaranteed that all constants c are positive integers.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10), representing the number of programs. Then, for each program, the input starts with an integer m (1 ≤ m ≤ 10) denoting the number of instructions in that program. The next m lines each contain one instruction, which can be one of the following forms:

• W
• Z
• + c (a plus sign, a space, and a positive integer constant)
• - c (a minus sign, a space, and a positive integer constant)

All programs start with x = 0 and y = 0 (for each program).

outputFormat

Output a single integer — the minimum possible final value of the global variable x after executing all programs concurrently.

sample

2
2
+ 5
Z
3
W
- 10
Z

-5