Mobile

Time Limit: 1000 ms Memory Limit: 30000 KiB

Problem 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 dL from the left and dR from the right,
an arm will balance if the product of the weight at the left
end and dL is equal to the product of the weight at the right
end and dR. (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,
2011 East Central Regional Contest
11
in order 1, 2, . . . , n, and will be in the form
dL dR typeL typeR nL nR
where dL and dR are integers ≤ 20 giving the distances from the pivot point to the left end and right
end of the arm, typeL and typeR are each either W or A, indicating that a weight or arm hangs from
the left or right ends, and nL and nR 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 ≤ w ≤ 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
109.

Sample Input

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

Sample Output

Case 1: 24
Case 2: 280

Hint


Source