E - Wrapping Chocolate Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君は N 枚のチョコレートを持っています。i 枚目のチョコレートは縦 A_i cm 横 B_i cm の長方形の形をしています。
また、高橋君は M 個の箱を持っています。i 個目の箱は縦 C_i cm 横 D_i cm の長方形の形をしています。

以下の条件を全て満たすように N 枚のチョコレートを全て箱に入れることは可能か判定してください。

  • 1 個の箱に入れることのできるチョコレートの数は、高々 1 個である
  • i 枚目のチョコレートを j 個目の箱に入れるとき、A_i \leq C_j かつ B_i \leq D_j を満たす必要がある（回転は不可）

制約

  • 1 \leq N \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i,C_i,D_i \leq 10^9
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 \ldots A_N
B_1 \ldots B_N
C_1 \ldots C_M
D_1 \ldots D_M

出力

N 枚のチョコレートを全て箱に入れることが可能ならば Yes と、不可能ならば No と出力せよ。

入力例 1

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

出力例 1

Yes

1 枚目のチョコレートを 3 個目の箱に入れて、2 枚目のチョコレートを 1 個目の箱に入れればよいです。

入力例 2

2 2
1 1
2 2
100 1
100 1

出力例 2

No

1 個の箱に入れることのできるチョコレートの数は、高々 1 個です。

入力例 3

1 1
10
100
100
10

出力例 3

No

入力例 4

1 1
10
100
10
100

出力例 4

Yes

Score : 500 points

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