Mobile#2682

Mobile

1 second

64 megabytes

Very easy

You have probably seen mobiles hanging from the ceilings of museums or airports. In this problem, we will focus on mobiles suspended from the ceiling by a single wire attached to a pivot point on an arm (which is also made of wire). At each end of the arm, there is either another wire suspending another arm, or a weight (usually in the form of some structure). One example, made by Alexander Calder, the best-known mobile artist, is shown below.

Some mobiles are simple, and some are quite complex. Besides their artistic value, they must be balanced. Recall that if the distance from the pivot point to the left is $d_{L}$ d_L and to the right is $d_{R}$ d_R, the arm will be balanced if the product of the weight at the left end and $d_{L}$ d_L is equal to the product of the weight at the right end and $d_{R}$ d_R. (The weight of the arms and the wires is ignored.)

For example, consider the mobile drawn below. If weight $1$ is $8$ units, then the weights $2$ , $3$ , $4$ , and $5$ must be $2$ , $6$ , $4$ , and $4$ units, respectively. If you know the structure of the mobile (i.e., the arrangement of arms and their pivot points) and the value of one weight, you can determine the values of all the weights. That is your task here—almost. The challenge is that all weights must be integers. You are given the minimum value for one weight and must set the other weights so that all are integers. Thus, the specified minimum weight may need to be increased slightly to achieve this.

Input

The input for each test case begins with a line containing a positive integer $n$ , the number of arms in the mobile. These arms are numbered from $1$ to $n$ . The next $n$ lines describe the arms in order and are of the form:

$d_{L} d_{R} type_{L} type_{R} n_{L} n_{R}$ d_L\ d_R\ \text{type}_L\ \text{type}_R\ n_L\ n_R

Here, $d_{L}$ d_L and $d_{R}$ d_R are integers ( $\leq 20$ ) giving the distances from the pivot point to the left and right ends of the arm; $type_{L}$ \text{type}_L and $type_{R}$ \text{type}_R are each either $W$ or $A$ , indicating that a weight or arm hangs from the corresponding end; and $n_{L}$ n_L and $n_{R}$ n_R are the indices of the weight or arm on the left and right, respectively. Indices for weights start at $1$ and are consecutive. The mobile will not have any arm hanging further down than $6$ arms from the top. In the example above, the lowest arm is $3$ arms from the top.

After the description of the arms, a line in the form $m w$ is given, indicating that weight $m$ must be at least $w$ , where $1 \leq w \leq 20$ 1 \leq w \leq 20.

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

Output

For each test case, output a single 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 $1 0^{9}$ 10^9.

Examples

Example 1