题目描述

Anastasia 喜欢在乌日兰迪亚中央公园散步。但她对单纯的散步失去了兴趣，于是开始收集乌日兰迪亚的小石子。一开始，她决定收集公园里能找到的所有小石子。

她只有两个口袋。每个口袋里最多可以同时放 $k$ 个小石子。公园里有 $n$ 种不同类型的小石子，第 $i$ 种类型的小石子有 $w_i$ 个。Anastasia 非常细心，她绝不会把不同类型的小石子放在同一个口袋里。然而，她可以在两个口袋分别放不同种类的小石子。不幸的是，她不能将所有时间都花在收集小石子上，所以她每天只能去公园收集一次小石子。

请你帮她计算，至少需要多少天可以把乌日兰迪亚中央公园里的所有小石子收集完，注意同一天里不能把不同类型的小石子放在同一个口袋中。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{5}$，$1 \leq k \leq 10^{9}$），分别表示不同类型小石子的种类数和每个口袋最多可容纳的小石子数。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$，其中 $w_i$（$1 \leq w_i \leq 10^4$）表示第 $i$ 种类型的小石子的数量。

输出格式

输出仅一行，表示收集完所有小石子最少需要的天数。

说明/提示

在第一个样例中，Anastasia 可以第一天收集第一种小石子，第二天收集第二种，第三天收集第三种。

第二个样例中最优操作如下：

• 第一天收集第三种小石子的 $8$ 个。
• 第二天收集第四种小石子的 $8$ 个。
• 第三天收集第一种小石子的 $3$ 个和第四种小石子的 $1$ 个。
• 第四天收集第五种小石子的 $7$ 个。
• 第五天收集第二种小石子 $1$ 个。

由 ChatGPT 5 翻译

样例

3 2
2 3 4

3

5 4
3 1 8 9 7

5