题目描述

安娜斯塔西娅喜欢去乌日扬迪安中央公园散步。但她对简单的散步不感兴趣，于是她开始收集公园里的鹅卵石。一开始，她决定收集所有她能在公园里找到的鹅卵石。

她只有两个口袋。她能在每个口袋里同时放最多 $k$ 个鹅卵石。第 $i$ 种鹅卵石有 $w_i$ 个。安娜斯塔西娅很有责任感，所以她从不把不同类型的鹅卵石混在一个口袋里。然而，她可以把不同种类的鹅卵石放在不同的口袋。不幸的是，她不能把所有的时间都花在收集鹅卵石上，所以她每天只能从公园里收集一次鹅卵石。

考虑到安娜斯塔西娅不能把不同类型的鹅卵石放在同一个口袋里，请帮助她找到收集乌日扬甸中央公园所有鹅卵石所需的最短天数。

输入格式

第一行两个整数 $n$、$k$，$n\le 10^5$，$k\le 10^9$。

第二行 $n$ 个整数分别为 $w_i$，$1\le w_i\le 10^4$。

输出格式

一个整数 $t$，为收集完所有鹅卵石的最少天数。

3 2
2 3 4

3

5 4
3 1 8 9 7

5