Problem Y
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}](/problems/tomography/file/statement/en/img-0001.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 |
