Score : $500$ points

问题描述

Takahashi 有 $N$ 块巧克力。第 $i$ 块巧克力呈矩形形状，宽度为 $A_i$ 厘米，长度为 $B_i$ 厘米。 他还拥有 $M$ 个盒子。第 $i$ 个盒子也呈矩形形状，宽度为 $C_i$ 厘米，长度为 $D_i$ 厘米。

判断在以下条件下是否有可能将这 $N$ 块巧克力放入盒子中：

• 每个盒子最多只能放一块巧克力。
• 当将第 $i$ 块巧克力放入第 $j$ 个盒子时，必须满足 $A_i \leq C_j$ 和 $B_i \leq D_j$（巧克力不能旋转）。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

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).

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.

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$

Output

If it is possible to put the $N$ pieces of chocolate in the boxes, print Yes; otherwise, print No.

Sample Input 1

2 3
2 4
3 2
8 1 5
2 10 5

Sample Output 1

Yes

We can put the first piece of chocolate in the third box and the second piece in the first box.

Sample Input 2

2 2
1 1
2 2
100 1
100 1

Sample Output 2

No

A box can contain at most one piece of chocolate.

Sample Input 3

1 1
10
100
100
10

Sample Output 3

No

Sample Input 4

1 1
10
100
10
100

Sample Output 4

Yes

update @ 2024/3/10 10:31:52