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 翻译