You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个 $n\times n$ 的矩阵，矩阵中的每个数都是整数。

现在要从矩阵中取 $m$ 个数，要求每一行最多取一个数，每一列也最多取一个数。

这 $m$ 个数的和最大能是多少？

输入格式

第一行两个数 $n$ 和 $m$ 。

接下来 $n$ 行，每行 $n$ 个数，表示矩阵。

输出格式

一行一个数，表示选择的 $m$ 个数的和最大是多少。

样例 1 输入

3 2
1 2 3
4 5 6
7 8 7

样例 1 输出

14

测试点约束

$50\%$ 的数据， $1\leq m\leq n\leq 3$ 。

$100\%$ 的数据， $1\leq m\leq 3, m\leq n\leq 15$ 。

矩阵中的数是不超过 $10^5$ 的正整数。