Type: Default 1000ms 256MiB

小鸡啄米模拟器

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

PDF DownLoad

本场竞赛的PDF题面:下载

Description

小鸡最近沉迷打卡,每天都要啄完若干堆米粒。

现在有 nn 堆米,第 ii 堆有 aia_i 粒米。小鸡每秒可以选择一堆还没啄完的米,并从中啄掉至多 kk 粒。如果这堆米剩下不到 kk 粒,它也会优雅地一口啄完,绝不浪费表情。

请问小鸡至少需要多少秒才能啄完所有米粒?

Format

Input

从标准输入读入数据。

第一行两个正整数 n,k(1≤n≤2×105,1≤k≤109)n,k(1 \le n \le 2 \times 10^5,1 \le k \le 10^9),表示米堆数量和小鸡每秒最多啄掉的米粒数。

第二行 nn 个正整数 a1,a2,…,an(1≤ai≤109)a_1,a_2,\ldots,a_n(1 \le a_i \le 10^9),表示每堆米的米粒数。

Output

输出一行一个整数,表示最少需要的秒数。

Samples

5 3
1 3 4 8 9
10

Note

样例说明:五堆米分别需要 1,1,2,3,31,1,2,3,3 秒,总共 1010 秒。