A - サーバーへのリクエスト分散 解説 /

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

配点 : 200 点

問題文

高橋君はウェブサービスの運用担当者です。彼の管理するシステムには N 台のサーバーがあり、明日から M 日間にわたる大規模キャンペーンが始まります。

キャンペーン期間中は、毎日ちょうど 1 件の重い処理リクエストが発生します。高橋君は M 日間の各日について、そのリクエストを N 台のサーバーのうちいずれか 1 台に必ず割り当てなければなりません。同じサーバーを複数の日に繰り返し選ぶこともできます。

各サーバー i（ 1 \leq i \leq N ）には「処理可能回数」 A_i が設定されています。キャンペーン期間全体を通じて、サーバー i に割り当てるリクエストの合計回数が A_i 回以下であれば、そのサーバーは正常に動作します。一方、A_i 回を超えるリクエストを割り当てると、そのサーバーはダウンしてしまいます。高橋君はどのサーバーもダウンさせてはなりません。

高橋君がうまくリクエストの割り当て先を選ぶことで、どのサーバーもダウンさせずに M 日間のキャンペーンを乗り切ることができるでしょうか？

乗り切ることが可能な割り当て方が存在するなら Yes を、存在しないなら No を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9（ 1 \leq i \leq N ）
  • 入力はすべて整数

入力

N M
A_1 A_2 \ldots A_N
  • 1 行目には、サーバーの台数を表す整数 N と、キャンペーンの日数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各サーバーの処理可能回数を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

どのサーバーもダウンさせずに M 日間のキャンペーンを乗り切ることが可能な割り当て方が存在するなら Yes を、存在しないなら No を 1 行で出力せよ。

入力例 1

3 10
3 4 2

出力例 1

No

入力例 2

5 100
10 20 30 15 25

出力例 2

Yes

入力例 3

4 1000000000
250000000 250000000 250000000 250000000

出力例 3

Yes

Score : 200 pts

Problem Statement

Takahashi is a web service operations manager. His system has N servers, and a large-scale campaign spanning M days starts tomorrow.

During the campaign period, exactly 1 heavy processing request occurs each day. For each of the M days, Takahashi must assign that request to exactly 1 of the N servers. The same server may be chosen on multiple days.

Each server i (1 \leq i \leq N) has a "processing capacity" A_i. If the total number of requests assigned to server i throughout the entire campaign period is at most A_i, that server operates normally. On the other hand, if more than A_i requests are assigned to it, that server will go down. Takahashi must not let any server go down.

Can Takahashi choose request assignments wisely enough to get through the M-day campaign without any server going down?

If there exists an assignment that allows all M days to be completed without any server going down, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N M
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of servers and an integer M representing the number of campaign days, separated by a space.
  • The second line contains N integers A_1, A_2, \ldots, A_N representing the processing capacity of each server, separated by spaces.

Output

If there exists an assignment that allows all M days of the campaign to be completed without any server going down, output Yes; otherwise, output No on a single line.

Sample Input 1

3 10
3 4 2

Sample Output 1

No

Sample Input 2

5 100
10 20 30 15 25

Sample Output 2

Yes

Sample Input 3

4 1000000000
250000000 250000000 250000000 250000000

Sample Output 3

Yes