Mobile

Time limit1sMemory limit256 MB

Summary

Given a tree of balanced arms with arm-length ratios, compute the minimum total weight when all weights are integers and one weight has a lower bound.

Level: Medium5 of 10
Topics: Tree, Math, Number theory
Solved: No attempts yet

Problem

A mobile hangs from the ceiling by a single wire attached to a pivot point on an arm. Each end of an arm carries either a weight or another arm, hung by its own wire. Write dL for the distance from the pivot point to the left end and dR for the distance to the right end. The arm balances when the weight $W_L$ hanging at the left end and the weight $W_R$ hanging at the right end satisfy

$W_L \times d_L = W_R \times d_R$

The weight hanging at an end is the total weight of everything below that end. The arms and the wires themselves weigh nothing.

In the mobile in the figure, if weight 1 weighs 8 units, then weights 2, 3, 4 and 5 weigh 2, 6, 4 and 4 units. Once you know the structure of a mobile and the value of one weight, every other weight is determined. Here every weight must be a positive integer, so you are given a lower bound instead of an exact value: weight m weighs at least w. Making all the weights integral sometimes forces weight m above w. Find the minimum total weight of the mobile.

Input

The input holds several test cases. Each test case starts with a line holding a positive integer n, the number of arms. The arms are numbered 1 to n. The next n lines describe arms 1 to n in order, each in this form:

dL dR typeL typeR nL nR

dL and dR are the distances from the pivot point to the left end and to the right end, each between 1 and 20. typeL and typeR are each W or A. W means a weight hangs from that end, A means another arm hangs from that end. nL and nR are the index of the weight or of the arm hanging there. The weight indices start at 1, run consecutively, and are all distinct. Exactly one arm hangs from no other arm, and that arm is the top one, attached to the ceiling. Counting the top arm as the first, no arm sits lower than the sixth, so n is at most 63.

After the n arm lines comes a line holding two integers m and w, meaning that weight m weighs at least w, with $1 \le w \le 20$ .

A line holding a single 0 follows the last test case.

Output

For each test case print one line in this form:

Case t: s

t is the number of the test case, counting from 1, and s is the minimum total weight of the mobile when every weight is a positive integer and weight m weighs at least w. Every answer is smaller than $10^9$ .

Examples2

Example 1

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

Expected output

Case 1: 24
Case 2: 280

Example 2
Input
```
1
1 1 W W 1 2
1 1
0
```
Expected output
```
Case 1: 2
```