모빌

천장에 매달린 모빌을 생각한다. 모빌은 하나의 줄로 천장에 매달려 있고, 그 줄은 막대(arm)의 한 지점인 받침점(pivot)에 연결된다. 막대의 양 끝에는 각각 또 다른 막대를 매단 줄이 있거나, 추(weight)가 달려 있다.

모빌은 균형을 이루어야 한다. 어떤 막대의 받침점에서 왼쪽 끝까지의 거리를 $d_L$, 오른쪽 끝까지의 거리를 $d_R$이라 하면, 이 막대는 다음 조건을 만족할 때 균형을 이룬다.

$$W_L \times d_L = W_R \times d_R$$

여기서 $W_L$은 왼쪽 끝에 매달린 전체 무게, $W_R$은 오른쪽 끝에 매달린 전체 무게이다. 막대와 줄 자체의 무게는 무시한다.

예를 들어 어떤 모빌에서 1번 추의 무게가 8이면 2, 3, 4, 5번 추의 무게는 각각 2, 6, 4, 4가 되어야 한다. 이처럼 모빌의 구조(막대들의 배치와 각 막대에서 받침점의 위치)와 추 하나의 무게를 알면 모든 추의 무게가 결정된다.

여기에 한 가지 조건이 더 있다. 모든 추의 무게는 정수여야 한다. 따라서 추 하나에 대해 원하는 최소 무게가 주어지면, 나머지 추들의 무게도 모두 정수가 되도록 값을 정해야 한다. 이때 지정된 추의 무게를 그 최소값보다 조금 크게 올려야 할 수도 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 막대의 개수를 나타내는 양의 정수 $n$이 적힌 줄로 시작한다. 막대에는 1번부터 $n$번까지 번호가 매겨진다.

이어지는 $n$개의 줄은 1번부터 $n$번까지 순서대로 각 막대를 다음 형식으로 설명한다.

dL dR typeL typeR nL nR

• $d_L$, $d_R$: 받침점에서 왼쪽 끝, 오른쪽 끝까지의 거리(각각 20 이하의 정수)
• $typeL$, $typeR$: 해당 끝에 추가 매달려 있으면 W, 막대가 매달려 있으면 A
• $n_L$, $n_R$: 왼쪽 끝, 오른쪽 끝에 매달린 추 또는 막대의 번호

추의 번호는 1번부터 시작하며 연속적이다. 어떤 막대도 맨 위에서 6단계보다 더 아래에 매달리지 않는다.

막대 설명 다음에는 m w 형식의 줄이 오며, 이는 $m$번 추의 무게가 최소 $w$임을 뜻한다($1 \le w \le 20$).

마지막 테스트 케이스 다음에는 $0$만 적힌 줄이 온다.

각 테스트 케이스마다 $m$번 추의 무게가 최소 $w$일 때 모빌 전체의 최소 무게를 한 줄에 출력한다. 각 답은 Case k: x 형식으로 출력하며, $k$는 1부터 시작하는 테스트 케이스 번호, $x$는 최소 무게이다. 모든 출력값은 $10^9$ 미만이라고 가정해도 된다.