AT_waipc_qual_b Prepare the Winning Game

$ 1 $ から $ N $ までの番号のついた $ N $ 頂点からなる重み付き完全無向グラフ $ G $ があります． 頂点 $ i $ と頂点 $ j $ ( $ 1 \leq i < j \leq N $ ) を結ぶ辺の重みは $ C_{i,j} $ です． Alice と Bob はこれからゲームをします． まずゲームの準備として，Bob が以下の操作を行います． - $ G $ から $ 0 $ 本以上の辺を削除する．ここで削除した辺の重みの総和を**コスト**と呼ぶことにする． - 頂点のうち好きな $ A $ 個を選び，そこに `A` と書き込む．残りの $ N-A $ 個に `B` と書き込む． - 好きな頂点を $ 1 $ 個選び，そこに駒を $ 1 $ つ置く． 準備が終了したらゲームを開始します． Alice から始めて二人のプレイヤーは交互に手番をプレイします． 各手番では，次のいずれかの行動ができます． - ゲームを終了する． - 駒を隣接頂点へと動かす．ただし，今までに駒が置かれたことのある頂点へは動かせない（ゲーム開始時に駒が置かれていた頂点にも動かせない）． ゲームが終了した瞬間に駒が置かれていた頂点に書かれた文字が `A` なら Alice の勝ち，`B` なら Bob の勝ちです． Bob は自分に必勝法が存在するようにゲームを準備したいです． そのために必要なコストの最小値を求めてください． $ 1 $ つの入力につき， $ T $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A $ $ C_{1,2} $ $ C_{1,3} $ $ \ldots $ $ C_{1,N} $ $ C_{2,3} $ $ \ldots $ $ C_{2,N} $ $ \vdots $ $ C_{N-1,N} $

各テストケースについて答えを出力せよ．

### Sample Explanation 1 $ 1 $ 番目のテストケースでは，以下のようにゲームを準備すればよいです． - 辺 $ (1,2) $ を削除する．コストが $ 1 $ かかる． - 頂点 $ 1,2 $ にそれぞれ `A`,`B` を書き込む． - 駒を頂点 $ 2 $ に置く． $ 2 $ 番目のテストケースでは，以下のようにゲームを準備すればよいです． - 辺 $ (1,2),(1,4) $ を削除する．コストが $ 0 $ かかる． - 頂点 $ 1,2,3,4 $ にそれぞれ `B`,`A`,`B`,`A` を書き込む． - 駒を頂点 $ 1 $ に置く． ### Constraints - $ 1 \leq T \leq 100 $ - $ 2 \leq N \leq 20 $ - $ 1 \leq A \leq N-1 $ - $ 0 \leq C_{i,j} \leq 10^9 $ - $ T $ ケースにわたる $ N^2 $ の総和は $ 20^2 $ 以下 - 入力はすべて整数