|
Темы:
Ford-Fulkerson algorithm
Consider a table of size MxN, in the cells of which there are non-negative integers. We say that a table is nice if for all i the sum of the numbers in its i-th row does not exceed Ri, and for all j the sum of the numbers in its j-th column does not exceed Cj.
You are given a table Z of size MxN, in some cells of which there are already non-negative integers. Find a nice table with the maximum sum of elements such that it matches Z on those cells where Z contains numbers.
Input
The first line of the input contains numbers M and N (1 <= M, N <= 20). The next line contains M non-negative integers - R1, R2, ..., RM. Next comes a line containing N non-negative integers C1, C2, ..., CN. All input limits do not exceed 106. The next M lines each contain N integers that define Z. If there is no number at some place in table Z, then -1 is in this place in the input data.
Imprint
Output the found table – M lines of N numbers. If there is no solution, print a single number -1.
Examples
| # |
Input |
Output |
| 1 |
2 2
1 10
1 10
-1 -1
-1 1 |
0 1
1 1 |
|