Ford-Fulkerson algorithm


Plus
Pin


Problem description Progress
ID 38633. cute tables
Темы: 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