Migrated from Lutece 732 Mobile

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You've probably seen mobiles suspended from the ceilings of museums or airports. We'll restrict our-selves to the type suspended from the ceiling by a single wire that is attached to a pivot point on an arm (also made of wire). At each end of the arm is either another wire suspending yet another arm, or a weight (usually in the form of some design). Below is one example, made by Alexander Calder, the best-known mobile artist.

Some mobiles are simple and some are quite complex. Be-sides the artistry, these must balance. Recall that from a pivot point distance $d_L$ from the left and $d_R$ from the right,an arm will balance if the product of the weight at the left end and $d_L$ is equal to the product of the weight at the right end and $d_R$. (We ignore the weight of the arm and the wires suspending the arms.)

For example, consider the mobile drawn below. If weight $1$ weighs $8$ units, then weights $2, 3, 4$, and $5$ must weigh $2, 6, 4$, and $4$ units respectively. In fact, if you know the structure of the mobile,that is, the arrangement of arms and where the pivot points are on each arm, and the value of one weight, you can determine the values of all the weights. That is your problem here { almost. It seems you only have weights that are integer valued. So, you'll be given the desired minimum value of one weight and determine the value of the other weights, so that those values will also be integers. Thus, it's possible that the specified minimum valued weight must be raised a little bit to accomplish this.

Input

Input for each test case will start with a line containing the positive integer $n$, indicating the number of arms in the mobile. These arms are numbered $1$ through $n$. The next $n$ lines will describe the arms,in order $1,2 \cdots n$, and will be in the form $d_L$ $d_R$ $type_L$ $type_R$ $n_L$ $n_R$ where $d_L$ and $d_R$ are integers $\le 20$ giving the distances from the pivot point to the left end and right end of the arm, $type_L$ and $type_R$ are each either $W$ or $A$, indicating that a weight or arm hangs from the left or right ends, and $n_L$ and $n_R$ are the index numbers of the weight or arm on the left and right.The indices for the weights will start at $1$ and be consecutive. The mobile will not have an arm that is hanging further down than $6$ arms from the top. In our example above the lowest arm is $3$ arms from the top.

Following the description of the arms is a line of the form $m$ $w$, indicating that weight $m$ weighs at least $w$, where $1 \le w \le 20$.

A line containing a $0$ follows the last test case

Output

For each test case output one line giving the minimum total weight of the mobile if weight $m$ is at least $w$. Use the format given in the Sample Output. You may assume all output values will be less than $10^9$.

Samples

4
3 1 W W 2 3
4 2 W A 1 3
2 2 A A 1 4
1 1 W W 4 5
1 8
4
2 2 A W 2 5
3 1 W A 4 3
4 1 W A 3 4
2 1 W W 1 2
3 20
0

Case 1: 24
Case 2: 280

Resources

2011 East Central Regional Contest