A - 応援要請 解説 /

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

配点 : 233 点

問題文

高橋君はイベント会場の設営リーダーです。今日は N 個のエリアにそれぞれ椅子を並べる作業があります。i 番目のエリアには A_i 脚の椅子を並べる必要があります。

椅子を並べる作業は 1 回の作業につき最大 K 脚 の椅子をまとめて運んで並べるというものです。ただし、1 回の作業では同一のエリアにしか椅子を運べません。したがって、i 番目のエリアの椅子をすべて並べるには \lceil A_i / K \rceil 回（A_i を K で割って切り上げた値）の作業が必要です。すべてのエリアの椅子を並べ終えるために必要な作業回数の合計は \displaystyle\sum_{i=1}^{N} \lceil A_i / K \rceil 回です。

高橋君のチームが今日中にこなせる作業回数の上限は、チーム全体の合計で M 回です。各作業をどのエリアに割り当てるかは自由です。

必要な作業回数の合計が M 回以下であれば、高橋君のチームだけで作業を完了できます。そうでない場合、高橋君は青木君に応援を要請します。応援要請 1 回につき、青木君が追加で 1 回の作業を行ってくれます。青木君の作業も上記と同じルールに従います（1 回の作業で最大 K 脚の椅子を同一のエリアに運んで並べる）。青木君が行った作業は高橋君のチームの上限 M 回には含まれず、青木君の作業をどのエリアに割り当てるかも自由です。応援の要請回数に上限はありませんが、高橋君は応援の要請回数をできるだけ少なく抑えたいと考えています。

すべてのエリアの椅子を並べ終えるために、高橋君が青木君に応援を要請する最小回数を求めてください。高橋君のチームだけですべての作業を完了できる場合は 0 を出力してください。

制約

  • 1 \leq N \leq 10^6
  • 0 \leq M \leq 10^{18}
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N M K
A_1 A_2 \ldots A_N
  • 1 行目には、エリアの数 N、高橋君のチーム全体が今日中にこなせる作業回数の上限 M、1 回の作業で運べる椅子の最大脚数 K が、スペース区切りで与えられる。
  • 2 行目には、各エリアに並べる椅子の脚数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべてのエリアの椅子を並べ終えるために必要な応援要請の最小回数を 1 行で出力せよ。高橋君のチームだけですべての作業を完了できる場合は 0 を出力せよ。

入力例 1

3 3 4
7 3 6

出力例 1

2

入力例 2

3 10 3
3 6 9

出力例 2

0

入力例 3

5 7 5
12 8 15 3 20

出力例 3

6

入力例 4

10 5 3
100 200 300 400 500 600 700 800 900 1000

出力例 4

1832

入力例 5

1 0 1
1

出力例 5

1

Score : 233 pts

Problem Statement

Takahashi is the setup leader for an event venue. Today, there is work to arrange chairs in each of N areas. The i-th area requires A_i chairs to be arranged.

The chair arrangement work involves carrying and arranging at most K chairs per single task. However, in a single task, chairs can only be carried to the same area. Therefore, arranging all the chairs in the i-th area requires \lceil A_i / K \rceil tasks (the value of A_i divided by K, rounded up). The total number of tasks needed to arrange all chairs in all areas is \displaystyle\sum_{i=1}^{N} \lceil A_i / K \rceil.

The maximum number of tasks that Takahashi's team can complete today is M in total for the entire team. They are free to assign each task to any area.

If the total number of required tasks is at most M, Takahashi's team can complete the work on their own. Otherwise, Takahashi requests backup from Aoki. For each backup request, Aoki performs one additional task. Aoki's tasks follow the same rules as above (carrying and arranging at most K chairs to the same area in one task). Tasks performed by Aoki are not counted toward Takahashi's team's limit of M tasks, and Aoki's tasks can be freely assigned to any area. There is no upper limit on the number of backup requests, but Takahashi wants to minimize the number of backup requests as much as possible.

Determine the minimum number of times Takahashi must request backup from Aoki in order to arrange all chairs in all areas. If Takahashi's team can complete all the work on their own, output 0.

Constraints

  • 1 \leq N \leq 10^6
  • 0 \leq M \leq 10^{18}
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N M K
A_1 A_2 \ldots A_N
  • The first line contains the number of areas N, the maximum number of tasks Takahashi's entire team can complete today M, and the maximum number of chairs that can be carried in one task K, separated by spaces.
  • The second line contains the number of chairs to be arranged in each area A_1, A_2, \ldots, A_N, separated by spaces.

Output

Output in a single line the minimum number of backup requests needed to arrange all chairs in all areas. If Takahashi's team can complete all the work on their own, output 0.

Sample Input 1

3 3 4
7 3 6

Sample Output 1

2

Sample Input 2

3 10 3
3 6 9

Sample Output 2

0

Sample Input 3

5 7 5
12 8 15 3 20

Sample Output 3

6

Sample Input 4

10 5 3
100 200 300 400 500 600 700 800 900 1000

Sample Output 4

1832

Sample Input 5

1 0 1
1

Sample Output 5

1