There is an $n \times n$ grid whose each square has some number of coins in it.
You know for each row and column how many squares you must choose from that row or column. You get all coins from every square you choose. What is the maximum number of coins you can collect and how could you choose the squares so that the given conditions are satisfied?
The first input line has an integer $n$ : the size of the grid. The rows and columns are numbered $1,2,\dots,n$ .
The next line has $n$ integers $a_1,a_2,\ldots,a_n$ : You must choose exactly $a_i$ squares from the $i$ th row.
The next line has $n$ integers $b_1,b_2,\ldots,b_n$ : You must choose exactly $b_j$ squares from the $j$ th column.
Finally, there are $n$ lines describing the grid. You can assume that the sums of $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ are equal.
First print an integer $k$ : the maximum number of coins you can collect. After this print $n$ lines describing which squares you choose ( X means that you choose a square, . means that you don't choose it).
If it is not possible to satisfy the conditions print only $-1$ .
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\n · · · · \n · · · · \n · · · · \n · · · · \n · · · · \n · · · · \n · · · · \n
32 ..... ..X.. .XX.X XX... .....\n \n \n \n \n \n