Hide

Problem C
Tomography

Binary tomography deals with the problem of reconstructing binary images from a small number of projections. One of its most basic problems is to construct a binary ($\{ 0,1\} $-valued) matrix with given row and column sums. This is not always possible and your task is to determine when it is.

Input

The first line of input contains two numbers $1\leq m,n\leq 1000$, the number of rows and columns of the matrix. The next line contains $m$ numbers $0\leq r_ i\leq n$ – the sum of each row in the matrix. The third line contains $n$ numbers $0\leq c_ j\leq m$ – the sum of each column in the matrix.

Output

Output “Yes” if there exists an $m$-by-$n$ matrix $\mathbf{A}$, with each element either beeing 0 or 1, such that

\[ \sum _{j=1}^ nA_{i,j} = r_ i \; \forall i\in \{ 1,2,\dots ,m\} \textrm{ and } \sum _{i=1}^ mA_{i,j} = c_ j \; \forall j\in \{ 1,2,\dots ,n\} . \]

Otherwise output “No”.

Example

The figure below illustrates a matrix with the row and column sums of sample input 1.

\includegraphics[width=4cm]{sample1.png}
Sample Input 1 Sample Output 1
3 4
2 3 2
1 1 3 2
Yes
Sample Input 2 Sample Output 2
3 3
0 0 3
0 0 3
No

Please log in to submit a solution to this problem

Log in