A - Package Delivery Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は配送センターの責任者で、M 件の届け先にすべての荷物を届けなければなりません。

配送センターには N 人のドライバーがいます。i 番目の届け先には A_i 個の荷物を届ける必要があります。

各ドライバーは複数の届け先の荷物を運ぶことができますが、1 人のドライバーが運ぶ荷物の個数の合計は K 個以下でなければなりません。同じ届け先の荷物を複数のドライバーで分担して届けることもできます。ただし、1 個の荷物をさらに分割することはできず、荷物は整数個単位で各ドライバーに割り当てます。荷物を運ばないドライバーがいても構いません。

すべての届け先のすべての荷物を、N 人のドライバーで漏れなく配送することが可能かどうか判定してください。

制約

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である

入力

N M K
A_1
A_2
\vdots
A_M

1 行目には、ドライバーの人数 N、届け先の数 M、1 人のドライバーが運べる荷物の最大個数 K がスペース区切りで与えられます。続く M 行のうち i 行目には、i 番目の届け先の荷物の個数 A_i が与えられます。

出力

すべての荷物を配送することが可能であれば Yes を、不可能であれば No を 1 行に出力してください。

入力例 1

3 4 5
2
4
3
1

出力例 1

Yes

入力例 2

2 3 4
3
4
2

出力例 2

No

入力例 3

6 8 7
5
10
3
6
4
7
2
5

出力例 3

Yes

入力例 4

19 20 1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
999999999

出力例 4

No

入力例 5

1 1 1
1

出力例 5

Yes

Score : 200 pts

Problem Statement

Takahashi is the manager of a delivery center and must deliver all packages to M destinations.

The delivery center has N drivers. The i-th destination requires A_i packages to be delivered.

Each driver can carry packages for multiple destinations, but the total number of packages carried by a single driver must be at most K. Packages for the same destination can be split among multiple drivers. However, a single package cannot be further divided, and packages must be assigned to each driver in whole numbers. It is acceptable for some drivers to carry no packages.

Determine whether it is possible for the N drivers to deliver all packages to all destinations without any omissions.

Constraints

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All input values are integers

Input

N M K
A_1
A_2
\vdots
A_M

The first line contains the number of drivers N, the number of destinations M, and the maximum number of packages a single driver can carry K, separated by spaces. The i-th of the following M lines contains A_i, the number of packages for the i-th destination.

Output

If it is possible to deliver all packages, print Yes; otherwise, print No on a single line.

Sample Input 1

3 4 5
2
4
3
1

Sample Output 1

Yes

Sample Input 2

2 3 4
3
4
2

Sample Output 2

No

Sample Input 3

6 8 7
5
10
3
6
4
7
2
5

Sample Output 3

Yes

Sample Input 4

19 20 1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
999999999

Sample Output 4

No

Sample Input 5

1 1 1
1

Sample Output 5

Yes