Mobile

Consider a mobile hanging from the ceiling. It is suspended by a single wire attached to a pivot point on an arm. At each end of an arm hangs either another wire holding a further arm, or a weight.

A mobile must balance. For an arm whose pivot point sits at distance $d_L$ from its left end and $d_R$ from its right end, the arm balances exactly when

$W_L \times d_L = W_R \times d_R$

where $W_L$ is the total weight hanging from the left end and $W_R$ is the total weight hanging from the right end. The weight of the arms and wires themselves is ignored.

For example, in one mobile, if weight 1 weighs 8 units, then weights 2, 3, 4, and 5 must weigh 2, 6, 4, and 4 units respectively. In general, once you know the structure of the mobile (how the arms are arranged and where each pivot point sits) and the value of a single weight, the values of all the weights are determined.

There is one extra condition: every weight must be an integer. So you are given the desired minimum value of one weight and must choose the other weights so that all of them are integers. To make this possible, the specified weight may have to be raised slightly above its given minimum.

The input consists of several test cases. Each test case begins with a line containing a positive integer $n$, the number of arms. The arms are numbered from 1 to $n$.

The next $n$ lines describe the arms, in order from 1 to $n$, each in the form

dL dR typeL typeR nL nR

• $d_L$, $d_R$: the distances from the pivot point to the left end and to the right end (each an integer at most 20).
• $typeL$, $typeR$: W if a weight hangs from that end, or A if an arm hangs from it.
• $n_L$, $n_R$: the index number of the weight or arm hanging from the left end and the right end.

Weight indices start at 1 and are consecutive. No arm hangs more than 6 levels below the top.

After the arm descriptions comes a line of the form m w, meaning that weight $m$ weighs at least $w$ ($1 \le w \le 20$).

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

For each test case, print one line with the minimum total weight of the mobile given that weight $m$ is at least $w$. Print each answer in the form Case k: x, where $k$ is the test case number starting from 1 and $x$ is the minimum total weight. You may assume every output value is less than $10^9$.