E - 荷物の配送トラック 解説 /

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

配点 : 433 点

問題文

高橋君は運送会社で働いています。今日は N 個の荷物を配送センターから届け先へ配送する必要があります。各荷物には 1 から N までの番号が付いており、荷物 i の重さは W_i キログラムです。

配送センターには M 台のトラックがあり、各トラックには 1 から M までの番号が付いています。トラック j の積載重量の上限は C_j キログラムであり、そのトラックに積んだ荷物の重さの合計が C_j キログラムを超えてはなりません。各トラックに積む荷物の個数についての制限はなく、荷物を 1 個も積まないトラックがあっても構いません。

各荷物は分割することができず、必ずちょうど 1 台のトラックに積まなければなりません。すべての N 個の荷物を、積載重量の上限を守りながらトラックに積むことが可能かどうかを判定してください。

制約

  • 1 \leq N \leq 15
  • 1 \leq M \leq 15
  • 1 \leq W_i \leq 10^8 (1 \leq i \leq N)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
W_1 W_2 \ldots W_N
C_1 C_2 \ldots C_M
  • 1 行目には、荷物の個数を表す N と、トラックの台数を表す M が、空白区切りで与えられる。
  • 2 行目には、各荷物の重さを表す W_1, W_2, \ldots, W_N が、空白区切りで与えられる。
  • 3 行目には、各トラックの積載重量の上限を表す C_1, C_2, \ldots, C_M が、空白区切りで与えられる。

出力

すべての荷物をトラックに積むことが可能であれば Yes を、不可能であれば No を出力してください。

入力例 1

3 2
3 5 2
6 4

出力例 1

No

入力例 2

4 2
10 20 30 40
50 50

出力例 2

Yes

入力例 3

8 3
15 25 30 10 20 35 5 40
80 60 50

出力例 3

Yes

Score : 433 pts

Problem Statement

Takahashi works at a shipping company. Today, he needs to deliver N packages from the distribution center to their destinations. Each package is numbered from 1 to N, and package i weighs W_i kilograms.

The distribution center has M trucks, each numbered from 1 to M. Truck j has a maximum load capacity of C_j kilograms, meaning the total weight of packages loaded onto that truck must not exceed C_j kilograms. There is no limit on the number of packages loaded onto each truck, and it is acceptable for a truck to carry no packages at all.

Each package cannot be split and must be loaded onto exactly one truck. Determine whether it is possible to load all N packages onto the trucks without exceeding any truck's maximum load capacity.

Constraints

  • 1 \leq N \leq 15
  • 1 \leq M \leq 15
  • 1 \leq W_i \leq 10^8 (1 \leq i \leq N)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
W_1 W_2 \ldots W_N
C_1 C_2 \ldots C_M
  • The first line contains N, the number of packages, and M, the number of trucks, separated by a space.
  • The second line contains W_1, W_2, \ldots, W_N, the weights of the packages, separated by spaces.
  • The third line contains C_1, C_2, \ldots, C_M, the maximum load capacities of the trucks, separated by spaces.

Output

If it is possible to load all packages onto the trucks, print Yes; otherwise, print No.

Sample Input 1

3 2
3 5 2
6 4

Sample Output 1

No

Sample Input 2

4 2
10 20 30 40
50 50

Sample Output 2

Yes

Sample Input 3

8 3
15 25 30 10 20 35 5 40
80 60 50

Sample Output 3

Yes