链接: https://cses.fi/problemset/task/2131

板块: Additional Problems II

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个 $n \times n$ 的网格，每个方格中有若干枚硬币。

你已知每一行和每一列必须选出的方格数量。你将从每一个选中的方格中获得其中的所有硬币。在满足给定条件的前提下，你最多能收集多少硬币？又该如何选择方格？

输入

第一行包含一个整数 $n$：网格大小。行和列编号为 $1,2,\dots,n$。

下一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$：第 $i$ 行必须恰好选中 $a_i$ 个方格。

下一行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$：第 $j$ 列必须恰好选中 $b_j$ 个方格。

最后有 $n$ 行描述网格（可假设 $\sum a_i = \sum b_j$）。

输出

先输出一个整数 $k$：能收集的最大硬币数。之后输出 $n$ 行描述选择（X 表示选中，. 表示不选）。

如果无法满足所有条件，只输出 $-1$。

数据范围

$1 \le n \le 50$ $0 \le a_i \le n$ $0 \le b_j \le n$ $0 \le c_{ij} \le 1000$

样例输入

5
0 1 3 2 0
1 2 2 0 1
2 5 1 5 1
0 2 5 1 2
3 8 9 3 5
1 4 3 7 3
0 3 6 2 8

样例输出

32
.....
..X..
.XX.X
XX...
.....