Bridge Construction Planning

A city is made up of many small islands, and its citizens live on those islands. Moving between islands requires a ferry, which the citizens find inconvenient. The mayor decided to build bridges that connect all the islands.

The city has two construction companies, A and B. The mayor asked both for quotes, and every proposal that came back has the form "company A (or company B) builds a bridge between island $u$ and island $v$ for $w$ hundred million yen".

The mayor wants to accept part of the proposals and end up with the cheapest plan. Accepting too many proposals from one company could bankrupt the other, and the city has only these two construction companies, so that outcome is unwelcome. To avoid complaints about wasteful construction, the mayor can accept only the smallest number of bridges that connects all the islands, that is $n-1$ of them. The mayor therefore decided to accept exactly $k$ proposals from company A and exactly $n-1-k$ proposals from company B.

Write a program that computes the cost of the cheapest plan meeting these conditions. The cost of a plan is the sum of the costs written in the accepted proposals.

The input consists of several datasets, at most 30 of them. Each dataset has the following format.

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

The first line holds three integers $n$, $m$, $k$, where $n$ is the number of islands, $m$ is the total number of proposals, and $k$ is the number of proposals to order from company A ($2 \le n \le 200$, $1 \le m \le 600$, $0 \le k \le n-1$). Islands are numbered 1 through $n$.

Each of the next $m$ lines holds one proposal as three integers $u_i$, $v_i$, $w_i$ and one character $l_i$, where $u_i$ and $v_i$ are the two islands the bridge joins, $w_i$ is the cost of the bridge in hundred million yen, and $l_i$ is the name of the company that submitted the proposal ($1 \le u_i \le n$, $1 \le v_i \le n$, $1 \le w_i \le 100$, and $l_i$ is 'A' or 'B'). Every bridge joins two distinct islands, so $u_i \ne v_i$. A company submits at most one proposal per pair of islands, so if $i \ne j$ and $l_i = l_j$ then $\{u_i, v_i\} \ne \{u_j, v_j\}$.

The end of the input is a line with three zeros separated by single spaces.

For each dataset, print the cost of the cheapest plan, in hundred million yen, as a single integer on its own line. If no plan meets the conditions, print -1.