问题 BN: kk与鹅卵石

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:156 通过:88

题目描述

KK喜欢到围垦公园散步。但她对简单的散步感到无聊,所以她开始收集围垦公园 的鹅卵石。起初,她决定收集在公园里能找到的所有鹅卵石。


她只有两个口袋。她最多可以在每个口袋里同时放上k颗卵石。公园里有n种不同类型的卵石,第i种类型的卵石有wi个。KK非常负责任,所以她从不把不同类型的鹅卵石混放在同一个口袋里。但是,她可以同时把不同种类的卵石放在不同的口袋里。不幸的是,她不能花所有的时间来收集卵石,所以她每天只能从公园里收集一次卵石。
考虑到KK不能把不同种类的鹅卵石放在同一个口袋里,请帮助她找出收集围垦公园的所有鹅卵石所需的最少天数。

输入格式

第一行包含两个整数n和k(1≤n≤1051≤k≤109)--不同卵石类型的数量和KK可以放在一个口袋中的卵石数量。
第二行包含n个整数w1,w2,...,wn (1≤wi≤104)--每种类型的鹅卵石的数量。

输出格式

一行输出包含一个整数--KK收集所有卵石所需的最小天数。
Examples
Input
3 2
2 3 4
Output
3
Input
5 4
3 1 8 9 7
Output
5
在第一个样例中,KK可以在第一天收集所有第一种类型的卵石,在第二天收集所有第二种类型的卵石,在第三天收集所有第三种类型的卵石。
在第二个样例中的最佳行动顺序。

    KK在第一天收集了8块第三种类型的卵石。
    第二天,她收集了8个第四种类型的卵石。
    第三天,她收集了3个第一类的卵石和1个第四类的卵石。
    第四天,她收集了7颗第五种类型的卵石。
    第五天,她收集了1个第二种类型的鹅卵石。

输入样例 复制

3 2
2 3 4


输出样例 复制

3

数据范围与提示