Score : 100 points
You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). A nonnegative integer A_{i,j} is written for each square (i,j).
You choose some of the squares so that each row and column contains at most K chosen squares. Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares. Additionally, calculate a way to choose squares that acheives the maximum.
Input is given from Standard Input in the following format:
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}
On the first line, print the maximum value of the sum of the integers written on the chosen squares.
On the next N lines, print a way that achieves the maximum.
Precisely, output the strings t_1,t_2,\cdots,t_N, that satisfies t_{i,j}=X
if you choose (i,j) and t_{i,j}=.
otherwise.
You may print any way to choose squares that maximizes the sum.
3 1 5 3 2 1 4 8 7 6 9
19 X.. ..X .X.
3 2 10 10 1 10 10 1 1 1 10
50 XX. XX. ..X