分数: 100 点
问题陈述
给你一个网格 N 行和 M 列。广场位于 i第行和 j第列将表示为 (i,j)。 非负整数 每个方格都写有 A_{i,j} 为每个方块写 (i,j).
你选择一些方格,使得每行和每列最多包含 K 选定的方块。 在此约束下,计算写在所选方格上的整数之和的最大值。 此外,计算一种选择达到最大值的方格的方法。
约束
- 1 \leq N \leq 50
- 1 \leq K \leq N
- 0 \leq A_{i,j} \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
输出
在第一行,打印所选方格上写入的整数之和的最大值。
上下 N 行,打印达到最大值的方式。
准确地说,输出字符串 t_1,t_2,\cdots,t_N,满足 t_{i,j}=X 如果您选择 (i,j) 和 t_{i,j}=. 否则。
您可以通过任何方式打印来选择使总和最大化的方块。
示例输入 1
3 1 5 3 2 1 4 8 7 6 9
示例输出 1
19 X.. ..X .X.
示例输入 2
3 2 10 10 1 10 10 1 1 1 10
示例输出 2
50 XX. XX. ..X