다리 건설 계획

작은 섬 여러 개로 이루어진 도시가 있고, 주민은 그 섬에 나뉘어 산다. 섬 사이를 배로만 오갈 수 있어 주민은 불편을 겪는다. 시장은 모든 섬을 잇는 다리를 놓기로 했다.

이 도시에는 건설 회사 A와 B가 있다. 시장이 두 회사에 견적을 요청해 받은 제안은 모두 "A사(또는 B사)가 섬 $u$와 섬 $v$를 잇는 다리를 $w$억 엔에 놓는다" 형태다.

시장은 제안 일부를 받아들여 예산이 가장 적은 계획을 세우려 한다. 그런데 한 회사의 제안만 너무 많이 받아들이면 다른 회사가 도산할 수 있고, 건설 회사가 둘뿐인 이 도시에 그런 상황은 바람직하지 않다. 한편 불필요한 공사라는 비판을 피하려면 모든 섬을 연결하는 데 필요한 최소 개수, 즉 $n-1$개의 다리만 받아들일 수 있다. 그래서 시장은 A사의 제안을 정확히 $k$개, B사의 제안을 정확히 $n-1-k$개 받아들이기로 정했다.

이 조건을 만족하는 계획 중 비용이 가장 적은 계획의 비용을 구하는 프로그램을 작성하라. 계획의 비용은 받아들인 제안에 적힌 비용의 합이다.

입력은 여러 개의 데이터 집합으로 이루어지고, 데이터 집합은 최대 30개다. 각 데이터 집합의 형식은 다음과 같다.

n m k
u1 v1 w1 l1
...
um vm wm lm

첫 줄에 정수 $n$, $m$, $k$가 주어진다. $n$은 섬의 수, $m$은 제안의 총 개수, $k$는 A사에 맡길 제안의 개수다 ($2 \le n \le 200$, $1 \le m \le 600$, $0 \le k \le n-1$). 섬은 1번부터 $n$번까지 번호로 구분한다.

이어지는 $m$줄에는 제안이 하나씩 주어지며, 각 줄은 정수 $u_i$, $v_i$, $w_i$와 문자 $l_i$로 이루어진다. $u_i$와 $v_i$는 다리가 잇는 두 섬, $w_i$는 다리의 비용(억 엔), $l_i$는 제안을 낸 회사의 이름이다 ($1 \le u_i \le n$, $1 \le v_i \le n$, $1 \le w_i \le 100$, $l_i$는 'A' 또는 'B'). 모든 다리는 서로 다른 두 섬을 잇는다. 즉 $u_i \ne v_i$다. 또 한 회사는 같은 섬 쌍에 제안을 최대 하나만 낸다. 즉 $i \ne j$이고 $l_i = l_j$이면 $\{u_i, v_i\} \ne \{u_j, v_j\}$다.

입력의 끝은 공백 하나로 구분한 0 세 개로 이루어진 줄로 표시한다.

각 데이터 집합마다 예산이 가장 적은 계획의 비용(억 엔)을 정수 하나로 한 줄에 출력한다. 조건을 만족하는 계획이 없으면 -1을 출력한다.