Hide

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 $A$ , with each element either beeing 0 or 1, such that

\sum_{j = 1}^{n} A_{i, j} = r_{i} \forall i \in {1, 2, \dots, m} and \sum_{i = 1}^{m} A_{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

Problem YTomography

Input

Output

Example

Problem Y
Tomography