整数规划

题目描述

度度熊有一个整数规划问题：

给定 n \times n 个整数 a_{i,j}（1 \le i, j \le n），要找出 2n 个整数 x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n，在满足：

$$ x_i + yj \le a{i,j} \quad (1 \le i, j \le n) $$

的约束下，最大化目标函数：

$$ \sum_{i=1}^{n} xi + \sum{i=1}^{n} y_i $$

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

输入

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

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

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

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

输出

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

样例

提示

• 1 \le T \le 20
• 1 \le n \le 200
• -10^9 \le a_{i,j} \le 10^9

来源

百度之星