AT_waipc_qual_b Prepare the Winning Game

有一个由 $N$ 个带编号 $1$ 至 $N$ 的顶点构成的带权完全无向图 $G$。顶点 $i$ 与顶点 $j$（$1 \leq i < j \leq N$）之间的边的权值为 $C_{i,j}$。 Alice 和 Bob 即将进行一场游戏。首先，在游戏准备阶段，Bob 会执行以下操作： - 从 $G$ 中删除 $0$ 条或多条边。被删除的边的权值之和称为**花费**（cost）。 - 从所有顶点中任选 $A$ 个，写上字母 `A`，其余 $N-A$ 个写上 `B`。 - 任选一个顶点，并在其上放置一个棋子。 准备完成后，游戏正式开始。Alice 先手，然后两名玩家轮流进行操作。每一回合，可以选择以下操作之一： - 结束游戏； - 将棋子移动到相邻顶点。前提是，不能移动到棋子曾经到达过的顶点（包括游戏开始时棋子所在的顶点）。 游戏结束时，若棋子停留的顶点上写着 `A`，则 Alice 获胜；若写着 `B`，则 Bob 获胜。Bob 希望通过准备（即边的删除、节点标记和初始棋子位置的选择）确保自己有必胜策略。请你求出实现必胜所需的最小花费。 请对每个输入，解答 $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}$

对每个测试用例，输出一行答案。

### 样例解释 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$。 ### 数据范围 - $1 \leq T \leq 100$ - $2 \leq N \leq 20$ - $1 \leq A \leq N-1$ - $0 \leq C_{i,j} \leq 10^9$ - 所有测试用例 $N^2$ 的和不超过 $20^2$ - 输入均为整数。 由 ChatGPT 5 翻译