D - 図書館の蔵書点検 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は図書館の司書として、 N 日間にわたる蔵書点検を担当しています。

この図書館には M 冊の本があります。本の劣化や破損を見逃さないため、各本 j (1 \leq j \leq M) は N 日間のうち少なくとも R_j 日は点検しなければならないという基準が設けられています。

一方、 i 日目 (1 \leq i \leq N) に点検できる本の冊数は最大で L_i 冊です。また、同じ日に同じ本を複数回点検することはできませんが、異なる日であれば同じ本を再び点検することができます。

高橋君はどの日にどの本を点検するかを自由に決めることができます。うまく点検計画を立てることで、すべての本の点検基準を満たすことが可能かどうかを判定してください。

すなわち、以下の条件をすべて満たすような点検計画が存在するかどうかを判定してください。

  • 各日 i に点検する本の冊数は L_i 冊以下である。
  • 同じ日に同じ本を2回以上点検することはない。
  • 各本 j が点検される日数の合計は R_j 日以上である。

制約

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

入力

N M
L_1 L_2 \ldots L_N
R_1 R_2 \ldots R_M
  • 1 行目には、点検期間の日数を表す N と、本の冊数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各日に点検できる本の最大冊数を表す L_1, L_2, \ldots, L_N が、スペース区切りで与えられる。
  • 3 行目には、各本の必要点検日数を表す R_1, R_2, \ldots, R_M が、スペース区切りで与えられる。

出力

すべての本の点検基準を満たすような点検計画が存在する場合は Yes を、存在しない場合は No を1行で出力せよ。

入力例 1

3 4
2 3 2
1 2 1 2

出力例 1

Yes

入力例 2

2 3
2 2
2 2 1

出力例 2

No

入力例 3

5 6
4 3 5 2 4
2 3 1 2 3 2

出力例 3

Yes

Score : 400 pts

Problem Statement

Takahashi is working as a librarian and is in charge of a book inspection spanning N days.

This library has M books. To ensure that no deterioration or damage to books is overlooked, a standard has been established that each book j (1 \leq j \leq M) must be inspected on at least R_j days out of the N days.

On the other hand, the maximum number of books that can be inspected on day i (1 \leq i \leq N) is L_i. Also, the same book cannot be inspected multiple times on the same day, but the same book can be inspected again on a different day.

Takahashi is free to decide which books to inspect on which days. Determine whether it is possible to create an inspection plan that satisfies the inspection requirements for all books.

Specifically, determine whether there exists an inspection plan that satisfies all of the following conditions:

  • The number of books inspected on each day i is at most L_i.
  • The same book is not inspected more than once on the same day.
  • The total number of days each book j is inspected is at least R_j.

Constraints

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

Input

N M
L_1 L_2 \ldots L_N
R_1 R_2 \ldots R_M
  • The first line contains N, the number of days in the inspection period, and M, the number of books, separated by a space.
  • The second line contains L_1, L_2, \ldots, L_N, the maximum number of books that can be inspected on each day, separated by spaces.
  • The third line contains R_1, R_2, \ldots, R_M, the required number of inspection days for each book, separated by spaces.

Output

If an inspection plan that satisfies the inspection requirements for all books exists, print Yes; otherwise, print No on a single line.

Sample Input 1

3 4
2 3 2
1 2 1 2

Sample Output 1

Yes

Sample Input 2

2 3
2 2
2 2 1

Sample Output 2

No

Sample Input 3

5 6
4 3 5 2 4
2 3 1 2 3 2

Sample Output 3

Yes