SP8666 ITRIX_C - Maximum - Profit -- Version II

查克拉是一位年轻有为的企业家，迅速成为了一名成功的酒店业者。他旗下拥有“Quickbyte”连锁餐厅，其中 $M$ 家餐厅已经全力运营。他将一天分为 $M$ 个时间段。在每个时间段 $j$，餐厅 $i$ 会有 $A_{ij}$ 名服务员和 $B_{ij}$ 名顾客。为了确保服务质量，他希望每位服务员在任何时间段内最多只服务一位顾客。由于查克拉的日程繁忙，每天每家餐厅仅在一个时间段内营业。因为一天内不同时段的饮食需求和顾客支付意愿不同，旺季或餐时的价格用 $C_{ij}$ 表示。现在，给定 $A_{ij}$、$B_{ij}$ 和 $C_{ij}$ 的值，求查克拉一天内能够获得的最大利润。 我们还有一个额外限制：“**每个时间段只能有一家餐厅营业**”。另外，餐厅数和时间段数相等，即均为 $M$。 **输入格式：** 第一行输入一个整数 $t$，代表测试用例的数量。 对每个测试用例，第一行有一个整数 $M$。 接下来的 $M$ 行，每行包含 $M$ 个整数，表示 $A_{ij}$ 的值。 接着的 $M$ 行，每行也包含 $M$ 个整数，表示 $B_{ij}$ 的值。 再接下来的 $M$ 行，每行同样包含 $M$ 个整数，表示 $C_{ij}$ 的值。 **输出格式：** 对于每个测试用例，输出查克拉一天里可获得的最大利润。 **示例** **输入：** ``` 2 2 1 2 3 2 3 2 1 2 4 5 3 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000 33 10 75 1000 1000 100 50 39 ``` **输出：** ``` 13 2050 ``` **数据范围与提示：** - $t \leq 50$ - $1 \leq M \leq 15$ - $1 \leq A_{ij}, B_{ij} \leq 5000$ - $0 \leq C_{ij} \leq 10^9$ **本翻译由 AI 自动生成**

无

无