9597: ABC245 —— E - Wrapping Chocolate
[Creator : ]
Description
Takahashi has $N$ pieces of chocolate. The $i$-th piece has a rectangular shape with a width of $A_i$ centimeters and a length of $B_i$ centimeters.
He also has $M$ boxes. The $i$-th box has a rectangular shape with a width of $C_i$ centimeters and a length of $D_i$ centimeters.
Determine whether it is possible to put the $N$ pieces of chocolate in the boxes under the conditions below.
- A box can contain at most one piece of chocolate.
- $A_i \leq C_j$ and $B_i \leq D_j$ must hold when putting the $i$-th piece of chocolate in the $j$-th box (they cannot be rotated).
He also has $M$ boxes. The $i$-th box has a rectangular shape with a width of $C_i$ centimeters and a length of $D_i$ centimeters.
Determine whether it is possible to put the $N$ pieces of chocolate in the boxes under the conditions below.
- A box can contain at most one piece of chocolate.
- $A_i \leq C_j$ and $B_i \leq D_j$ must hold when putting the $i$-th piece of chocolate in the $j$-th box (they cannot be rotated).
Input
Input is given from Standard Input in the following format:
```
$N$ $M$
$A_1$ $\ldots$ $A_N$
$B_1$ $\ldots$ $B_N$
$C_1$ $\ldots$ $C_M$
$D_1$ $\ldots$ $D_M$
```
```
$N$ $M$
$A_1$ $\ldots$ $A_N$
$B_1$ $\ldots$ $B_N$
$C_1$ $\ldots$ $C_M$
$D_1$ $\ldots$ $D_M$
```
Output
If it is possible to put the $N$ pieces of chocolate in the boxes, print `Yes`; otherwise, print `No`.
Constraints
- $1 \leq N \leq M \leq 2\times 10^5$
- $1 \leq A_i,B_i,C_i,D_i \leq 10^9$
- All values in input are integers.
- $1 \leq A_i,B_i,C_i,D_i \leq 10^9$
- All values in input are integers.
Sample 1 Input
2 3
2 4
3 2
8 1 5
2 10 5
Sample 1 Output
Yes
We can put the first piece of chocolate in the third box and the second piece in the first box.
Sample 2 Input
2 2
1 1
2 2
100 1
100 1
Sample 2 Output
No
A box can contain at most one piece of chocolate.
Sample 3 Input
1 1
10
100
100
10
Sample 3 Output
No
1 1
10
100
10
100
Yes