整数规划

度度熊有一个可能是整数规划的问题：

给定 $n \times n$ 个整数 $a_{i,j}(1 \leq i,j \leq n)$，要找出 $2n$ 个整数 $x_1$,$x_2$,…,$x_n$,$y_1$,$y_2$,…,$y_n$ 在满足 $x_i+y_j \leq a_{i,j}(1 \leq i,j \leq n)$ 的约束下最大化目标函数 $\sum_{i=1}^{n} x_i + \sum_{i=1}^{n} y_i$，

你需要帮他解决这个整数规划问题，并给出目标函数的最大值。

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据：

第一行包含一个整数 $n$，表示该整数规划问题的规模。

接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 列的元素是 $a_{i,j}$。

保证 $ 1 \leq T \leq 20$，$1 \leq n \leq 200$，$-10^9 \leq a_{i,j} \leq 10^9(1 \leq i,j \leq n)$。

对于每组测试数据，输出一行信息 "Case #x: y"（不含引号），其中 x 表示这是第 $x$ 组测试数据，y 表示目标函数的最大值，行末不要有多余空格。

2
1
0
2
1 2
3 4

Case #1: 0
Case #2: 5

2018"百度之星"程序设计大赛 - 资格赛