← 返回题目列表

Codeforces · 789/A

A. 阿纳斯塔西娅和鹅卵石

中文机器翻译题面 查看原题

阿纳斯塔西娅喜欢在中央乌日良迪安公园散步。但她对简单的步行不再感兴趣,因此她开始收集乌兹良迪亚的鹅卵石。起初,她决定收集公园里能找到的所有鹅卵石。

她只有两个口袋。她最多可以同时在每个口袋里放入 k 颗鹅卵石。公园里有 n 种不同的卵石类型,并且有 wi 个第 i 种类型的卵石。阿纳斯塔西娅非常负责任,所以她从不把不同类型的鹅卵石混放在同一个口袋里。然而,她可以同时将不同种类的鹅卵石放入不同的口袋中。不幸的是,她不能把所有的时间都花在收集鹅卵石上,所以她每天只能从公园收集一次鹅卵石。

考虑到阿纳斯塔西娅不能将不同类型的鹅卵石放在同一个口袋里,请帮助她找到收集乌兹利亚中央公园所有鹅卵石所需的最少天数。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109) - 不同卵石类型的数量以及 Anastasia 可以放入一个口袋中的卵石数量。

第二行包含 n 个整数 w1, w2, ..., wn (1 ≤ wi ≤ 104) - 每种类型的卵石数量。

输出

输出的唯一一行包含一个整数——阿纳斯塔西娅收集所有卵石所需的最少天数。

示例

输入 #1

3 2
2 3 4

输出 #1

3

输入 #2

5 4
3 1 8 9 7

输出 #2

5

注意

在第一个示例案例中,Anastasia 可以在第一天收集所有第一种类型的卵石,在第二天收集第二种类型的所有卵石,在第三天收集第三种类型的所有卵石。

第二个示例案例中的最佳操作顺序:

- 第一天阿纳斯塔西娅收集了 8 个第三种类型的卵石。
- 第二天她收集了 8 颗第四种类型的鹅卵石。
- 第三天,她收集了 3 个第一种类型的卵石和 1 个第四种类型的卵石。
- 第四天她收集了 7 颗第五种鹅卵石。
- 第五天,她收集了 1 个第二种类型的卵石。