Migrated from Lutece 1255 斓少摘苹果

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

斓少家的院子里有$N$棵苹果树，每到秋天树上就会结出$F_i$个苹果。

苹果成熟的时候，斓少就会跑去摘苹果。

斓少摘苹果的方式非常的奇特，每次最多可以选择$M$个苹果并摘下来。

但是摘下来的苹果两两一定不是来自同一棵树，问斓少最少摘多少次，才能使得每个苹果都被摘下来呢？

Input

第一行输入一个数$N$和$M$（$1 \leq M \leq N \leq 10^6$），代表苹果树的数量，和斓少每次最多摘多少个。

第二行输入$N$个数，第$i$个数$F_i$（$0 \leq F_i \leq 10^6$）代表这一棵树上一共有多少个苹果

Output

输出一个数字，表示最少选择次数

Samples

5 3
3 2 3 2 4

5

Note

样例可以选 (1,3,5) (2,3,5) (1,4,5) (1,2,5) (3,4) 共5次

Resources

第七届ACM趣味程序设计竞赛第二场（正式赛）