D - Network Construction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、N 台のサーバーを管理しています。それぞれのサーバーには 1 から N までの番号が付けられており、サーバー i の通信負荷は A_i です。

高橋君は、これらのサーバーをネットワークケーブルで接続し、すべてのサーバーが直接または他のサーバーを経由して互いに通信できる連結なネットワークを構築しようとしています。N = 1 のときは、ケーブルを使用せずとも連結であるとみなします。

高橋君は M 本のネットワークケーブルを持っており、ケーブル j の帯域幅は L_j です。高橋君は、各ケーブルについて、異なる 2 台のサーバーを選んでそのケーブルで接続することができます。ただし、サーバー u とサーバー v（u \neq v）をケーブル j で接続するには、ケーブルの帯域幅が両方のサーバーの通信負荷の和以上であること、すなわち L_j \geq A_u + A_v を満たす必要があります。

ケーブルの使用には以下の制約があります。

  • 各ケーブルは高々 1 組のサーバーペアの接続にしか使用できません。使用しないケーブルがあってもかまいません。
  • 同じ 2 台のサーバーの間に複数のケーブルを接続することはできません。ただし、ネットワーク全体として閉路を含むことは許されます。

すべてのサーバーを 1 つの連結なネットワークにまとめることができるかどうか判定し、できる場合は Yes を、できない場合は No を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
A_1 A_2 \ldots A_N
L_1 L_2 \ldots L_M
  • 1 行目には、サーバーの台数を表す整数 N と、ケーブルの本数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各サーバーの通信負荷を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各ケーブルの帯域幅を表す整数 L_1, L_2, \ldots, L_M が、スペース区切りで与えられる。

出力

すべてのサーバーを 1 つの連結なネットワークにまとめることができる場合は Yes を、できない場合は No を 1 行で出力してください。

入力例 1

3 2
1 2 3
4 5

出力例 1

Yes

入力例 2

4 5
3 1 4 2
5 6 4 7 3

出力例 2

Yes

入力例 3

5 3
10 20 30 40 50
25 35 45

出力例 3

No

Score : 400 pts

Problem Statement

Takahashi manages N servers. Each server is numbered from 1 to N, and the communication load of server i is A_i.

Takahashi is trying to connect these servers with network cables to build a connected network where all servers can communicate with each other, either directly or through other servers. When N = 1, the network is considered connected without using any cables.

Takahashi has M network cables, and the bandwidth of cable j is L_j. For each cable, Takahashi can choose two distinct servers and connect them with that cable. However, to connect server u and server v (u \neq v) with cable j, the bandwidth of the cable must be at least the sum of the communication loads of both servers, i.e., L_j \geq A_u + A_v must be satisfied.

The following constraints apply to the use of cables:

  • Each cable can be used to connect at most one pair of servers. It is acceptable to leave some cables unused.
  • Multiple cables cannot be connected between the same two servers. However, the network as a whole is allowed to contain cycles.

Determine whether it is possible to connect all servers into a single connected network. If it is possible, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers

Input

N M
A_1 A_2 \ldots A_N
L_1 L_2 \ldots L_M
  • The first line contains two integers separated by a space: N, the number of servers, and M, the number of cables.
  • The second line contains N integers separated by spaces: A_1, A_2, \ldots, A_N, representing the communication load of each server.
  • The third line contains M integers separated by spaces: L_1, L_2, \ldots, L_M, representing the bandwidth of each cable.

Output

If it is possible to connect all servers into a single connected network, output Yes; otherwise, output No, in a single line.

Sample Input 1

3 2
1 2 3
4 5

Sample Output 1

Yes

Sample Input 2

4 5
3 1 4 2
5 6 4 7 3

Sample Output 2

Yes

Sample Input 3

5 3
10 20 30 40 50
25 35 45

Sample Output 3

No