모빌

모빌은 천장에서 내려온 줄 하나가 막대의 받침점에 매달린 구조다. 막대의 양 끝에는 추가 달려 있거나, 다른 줄에 매달린 또 다른 막대가 달려 있다. 받침점에서 왼쪽 끝까지의 거리를 dL, 오른쪽 끝까지의 거리를 dR이라고 하자. 왼쪽 끝에 매달린 무게 $W_L$과 오른쪽 끝에 매달린 무게 $W_R$이 다음 식을 만족할 때 그 막대는 균형을 이룬다.

$W_L \times d_L = W_R \times d_R$

한쪽 끝에 매달린 무게란 그 끝 아래에 있는 모든 것의 무게를 더한 값이다. 막대와 줄 자체의 무게는 무시한다.

그림의 모빌에서 추 1의 무게가 8이면 추 2, 3, 4, 5의 무게는 각각 2, 6, 4, 4가 된다. 이렇게 모빌의 구조와 추 하나의 무게를 알면 나머지 추의 무게가 모두 정해진다. 이 문제에서는 추의 무게가 모두 양의 정수여야 하므로, 정확한 무게 대신 하한을 준다. 추 m의 무게는 w 이상이어야 한다. 모든 무게를 정수로 맞추다 보면 추 m의 무게를 w보다 무겁게 잡아야 할 때도 있다. 모빌 전체 무게의 최솟값을 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 막대의 개수인 양의 정수 n이 주어진다. 막대의 번호는 1번부터 n번까지다. 다음 n개 줄에는 1번 막대부터 n번 막대까지 차례대로 다음 형식의 정보가 주어진다.

dL dR typeL typeR nL nR

dL과 dR은 받침점에서 왼쪽 끝과 오른쪽 끝까지의 거리이며, 각각 1 이상 20 이하다. typeL과 typeR은 각각 W 또는 A다. W는 그 끝에 추가 달렸다는 뜻이고, A는 다른 막대가 달렸다는 뜻이다. nL과 nR은 그 끝에 달린 추 또는 막대의 번호다. 추의 번호는 1번부터 빠짐없이 이어지며 서로 겹치지 않는다. 다른 막대에 매달리지 않은 막대는 정확히 하나이고, 그 막대가 천장에 매달린 맨 위 막대다. 맨 위 막대를 첫 번째로 셀 때 여섯 번째보다 아래에 있는 막대는 없으므로, n은 63 이하다.

막대를 설명하는 n개 줄 다음에는 두 정수 m과 w가 한 줄에 주어진다. 추 m의 무게가 w 이상이어야 한다는 뜻이며, $1 \le w \le 20$이다.

마지막 테스트 케이스 다음 줄에는 0 하나만 주어진다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case t: s

t는 1부터 세는 테스트 케이스 번호이고, s는 모든 추의 무게가 양의 정수이면서 추 m의 무게가 w 이상일 때 모빌 전체 무게의 최솟값이다. 모든 답은 $10^9$보다 작다.