Условие:
ограничение по времени на тест: 3 s .
ограничение по памяти на тест: 1024 MB
В вашем плейлисте на сайте MeValve сейчас содержится n очень интересных и познавательных видео. i-е видео длится ровно di минут.
MeValve в своей обычной манере увеличил частоту и продолжительность показа рекламы. Во вселенной добра и справедливости, где вы находитесь, реклама на MeValve показывается только МЕЖДУ видео. После видео реклама показывается тогда и только тогда, когда соблюдается любое из условий ниже:
- с показа последней рекламы было просмотрено 3 видео;
- с показа последней рекламы прошло хотя бы k минут.
Для выполнения домашней работы вам срочно нужно посмотреть все n видео в вашем плейлисте. Зная, что вы только что просмотрели рекламный ролик, выберите такой порядок просмотра видео, чтобы минимизировать количество просмотренных рекламных вставок. Следующее видео начинается сразу после того, как заканчивается предыдущее видео либо реклама, и после последнего ролика рекламу смотреть не обязательно (шах и мат, Googleплекс) |
Входные данные
В первой строке записано единственное целое число t(1 ≤ t ≤ 100000) - Количество наборов входных данных.
Первая строка каждого набора состоит из пары натуральных чисел n и k(1 ≤ n ≤ 100000,1 ≤ k ≤ 30000) - количество видео и временной интервал между показами рекламы соответственно.
В следующей строке даны n чисел d{1}, d{2}, \ldots, d{n}≤ft(1 ≤ d{i} ≤ 10000\right) - продолжительности роликов в плейлисте.
Сумма n по всем тестам не превосходит 106.
Выходные данные
В ответ на каждый тестовый набор выведите минимальное количество рекламных роликов, которое необходимо посмотреть.
Пример
\begin{tabular}{|l|l|}
\hline входные данные & Скопировать \\
\hline μlticolumn{2}{|l|}{5} \\
\hline 825 & \\
\hline μlticolumn{2}{|l|}{\begin{array}{llllllll}4 & 5 & 18 & 3 & 17 & 17 & 18 & 14\end{array}} \\
\hline μlticolumn{2}{