0040 - 橋の建造計画

多くの小島からなる市があり，市民はそれらの島に住んでいる． 島から島へ渡るにはフェリーを使うしかなく，多くの市民は不便に感じている． そこで市長はすべての島を互いに行き来できるように橋を架けることにした．

市にはふたつの建設会社（A社とB社）がある． 市長がこれらに見積もりを請求し，いくつかの提案を次の形で得た： 「建設会社 A (または B) は島 u と島 v の間を結ぶ橋を w 億円で建造できる」．

市長はこれらの提案のうちいくつかを採用することで最も安い建造計画を作ろうとしている． ところが，もし市長が一方の会社の提案を多く採用すると，もう一方の会社は潰れてしまう． これはたったふたつしか建設会社がない市にとっては望ましくない． しかし一方で，無駄な建設だという批判を避けるには，全ての島を行き来できるようにするために必要最低限の本数の橋 (すなわち n−1 本の橋) しか採用できない． そこで，市長は予め建設会社 A の提案を丁度 k 個，建設会社 B の提案を丁度 n−1−k 個採用することに決めた．

あなたの仕事は，条件を満たす中で最も安い計画の費用を計算するプログラムを作ることである． ここで，計画の費用とは採用されるすべての提案の費用の合計のことをいう．

入力は複数のデータセットからなる． データセットの数は 30 以下である． 各データセットは次の形式で表される．

n m k
u₁ v₁ w₁ l₁
...
u_m v_m w_m l_m

最初の行にはみっつの整数 n, m, k が含まれており，それぞれ n は島の数，m は提案の総数，k は A 社から採用する提案の数を意味する (2 ≤ n ≤ 200, 1 ≤ m ≤ 600, 0 ≤ k ≤ n−1)． 島は 1 から n までの整数で表されている． 続く m 行は提案の情報を示しており，各提案はみっつの整数 u_i, v_i, w_i とひとつの文字 l_i によって表されている．ここで u_i と v_i は橋の両端の島，w_i はその橋を架ける値段（億円）， そして l_i は見積もりを提出した建設会社の名前を意味している (1 ≤ u_i ≤ n, 1 ≤ v_i ≤ n, 1 ≤ w_i ≤ 100, l_i = 'A' または 'B')． 橋は相異なる島を結ぶものとしてよい，すなわち u_i ≠ v_i である． また，各会社は島の対に対して高々ひとつの提案を出すものとしてよい，すなわち i ≠ j かつ l_i = l_j のとき {u_i, v_i} ≠ {u_j, v_j} である．

入力の終わりは，空白ひとつで区切られたゼロみっつからなる行で表される．

各データセットについて，条件を満たす一番安い計画の費用（億円）を出力せよ． 条件を満たす計画が存在しない場合は −1 と出力すること．

4 5 2
1 2 2 A
1 3 2 A
1 4 2 A
2 3 1 B
3 4 1 B
5 8 2
1 2 1 A
2 3 1 A
3 4 3 A
4 5 3 A
1 2 5 B
2 3 5 B
3 4 8 B
4 5 8 B
5 5 1
1 2 1 A
2 3 1 A
3 4 1 A
4 5 1 B
3 5 1 B
4 5 3
1 2 2 A
2 4 3 B
3 4 4 B
2 3 5 A
3 1 6 A
0 0 0

5
16
-1
-1