A. Анастасия и камушки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Анастасия очень любит гулять в Центральном Ужляндском Парке. Но просто гулять ей стало неинтересно, поэтому она начала коллекционировать ужляндские камушки. Сначала она решила собрать все камушки, которые найдет в парке.

У неё есть всего два кармана. В каждом кармане помещается до k камушков. В парке можно найти камушки n видов, причем камушков i-го типа в парке ровно wi штук. Анастасия очень ответственно относится к новому хобби, поэтому она никогда не смешает камушки двух разных видов в одном кармане. Но это не мешает ей класть камушки одного вида в разные карманы. К сожалению, она не может тратить всё своё время на сбор камушков, поэтому она может приносить камушки из парка только один раз за день.

Помогите ей узнать минимальное количество дней, необходимое для того, чтобы собрать все камушки Ужляндского парка. Помните, что Анастасия не может переносить в одном кармане камушки разных видов одновременно.

Входные данные

В первой строке входных данных содержится два числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109) — количество видов камушков и количество камушков, которые помещаются в каждый карман.

Во второй строке содержится n целых чисел w1, w2, ..., wn (1 ≤ wi ≤ 104) — количество камушков каждого из видов.

Выходные данные

Выведите одно целое число — минимальное количество дней, которое понадобится Анастасии, чтобы собрать все камушки Ужляндского парка.

Примеры
Входные данные
3 2
2 3 4
Выходные данные
3
Входные данные
5 4
3 1 8 9 7
Выходные данные
5
Примечание

В первом примере в первый день Анастасия может собрать все камушки первого вида, во второй день — второго вида, в третий — третьего.

Во втором примере одним из оптимальных ответов является такой:

  • В первый день Анастасия собирает 8 камушков третьего вида.
  • Во второй день она собирает 8 камушков четвертого вида.
  • В третий день она собирает 3 камушка первого вида и 1 камушек четвертого.
  • В четвертый день она собирает 7 камушков пятого вида.
  • В пятый день она собирает 1 камушек второго вида.