영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There is an n × 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?
Input
The first input line has an integer n: the size of the grid. The rows and columns are numbered 1,2,…,n.
The next line has n integers a_1,a_2,…,a_n: You must choose exactly a_i squares from the ith row.
The next line has n integers b_1,b_2,…,b_n: You must choose exactly b_j squares from the jth column.
Finally, there are n lines describing the grid. You can assume that the sums of a_1,a_2,…,a_n and b_1,b_2,…,b_n are equal.
Output
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.
Constraints
- 1 ≤ n ≤ 50
- 0 ≤ a_i ≤ n
- 0 ≤ b_j ≤ n
- 0 ≤ c_ij ≤ 1000
예제
예제 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
32 ..... ..X.. .XX.X XX... .....