D - Distribution of Souvenirs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は修学旅行の班長を務めています。班には高橋君を含めて N 人のメンバーがおり、高橋君はお土産屋で M 種類のお菓子を購入しました。i 番目の種類のお菓子は C_i 個あります。

高橋君はこれらのお菓子を班のメンバー全員（高橋君自身を含む N 人）に配ろうとしています。配り方のルールは以下の通りです：

  • 各メンバーにはちょうど K 個のお菓子を配る。
  • お菓子の各個体は 1 人のメンバーにのみ配ることができる。すなわち、i 番目の種類のお菓子は合計で C_i 個までしか配ることができない。
  • 同じ種類のお菓子を同じメンバーに 2 個以上配ってはならない。すなわち、各メンバーが受け取る K 個のお菓子はすべて異なる種類でなければならない。ただし、異なるメンバーが同じ種類のお菓子をそれぞれ受け取ることは許される。
  • お菓子を余らせても構わない。

すべてのメンバーにちょうど K 個ずつお菓子を配ることが可能かどうかを判定してください。可能であれば Yes を、不可能であれば No を出力してください。

制約

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • 入力はすべて整数である。

入力

N M K
C_1 C_2 \ldots C_M
  • 1 行目には、班のメンバーの人数を表す N 、お菓子の種類数を表す M 、各メンバーに配るお菓子の個数を表す K が、スペース区切りで与えられる。
  • 2 行目には、各種類のお菓子の個数を表す C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。

出力

すべてのメンバーにちょうど K 個ずつお菓子を配ることが可能であれば Yes を、不可能であれば No を 1 行で出力せよ。

入力例 1

3 4 2
3 3 3 3

出力例 1

Yes

入力例 2

5 3 3
2 2 2

出力例 2

No

入力例 3

1000000000 5 3
1000000000 1000000000 500000000 500000000 999999999

出力例 3

Yes

Score : 400 pts

Problem Statement

Takahashi is the group leader for a school trip. The group has N members including Takahashi, and Takahashi purchased M types of sweets at a souvenir shop. There are C_i pieces of the i-th type of sweet.

Takahashi wants to distribute these sweets to all members of the group (N people including himself). The rules for distribution are as follows:

  • Each member receives exactly K sweets.
  • Each individual sweet can be given to only one member. That is, at most C_i pieces of the i-th type of sweet can be distributed in total.
  • No member may receive 2 or more sweets of the same type. That is, the K sweets each member receives must all be of different types. However, different members are allowed to each receive sweets of the same type.
  • It is acceptable to have leftover sweets.

Determine whether it is possible to distribute exactly K sweets to every member. If it is possible, output Yes; otherwise, output No.

Constraints

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • All input values are integers.

Input

N M K
C_1 C_2 \ldots C_M
  • The first line contains N representing the number of group members, M representing the number of types of sweets, and K representing the number of sweets to give to each member, separated by spaces.
  • The second line contains C_1, C_2, \ldots, C_M representing the number of pieces of each type of sweet, separated by spaces.

Output

If it is possible to distribute exactly K sweets to every member, output Yes; otherwise, output No on a single line.

Sample Input 1

3 4 2
3 3 3 3

Sample Output 1

Yes

Sample Input 2

5 3 3
2 2 2

Sample Output 2

No

Sample Input 3

1000000000 5 3
1000000000 1000000000 500000000 500000000 999999999

Sample Output 3

Yes