В некоторой лаборатории к потолку подвешено $$$n$$$ лазеров. Изначально каждый лазер подвешен на расстоянии $$$a_i$$$ от потолка. При этом все лазеры висят в одной плоскости, и у каждого есть своя уникальная координата $$$x_i = i$$$.
На другом конце комнаты стоит экран. Все лазеры излучают свет в сторону экрана, поэтому если $$$2$$$ лазера висят на одной высоте, то свет из лазера с меньшей координатой не доходит до экрана.
Вы можете не более $$$k$$$ раз взять какой-то лазер и увеличить его расстояние от потолка на $$$1$$$. Вас интересует — при оптимальном использовании операции, свет какого наибольшего числа лазеров будет регистрироваться экраном?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит $$$2$$$ целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — общее число лазеров и число операций соответственно.
Вторая строка каждого набора входных данных содержит через пробел $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — изначальные расстояния от лазеров до потолка.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите в единственной строке целое число — максимальное количество лазеров, свет от которых попадает на экран после применения не более $$$k$$$ операций.
34 41 2 3 44 51 1 1 19 24 3 3 10 5 5 5 99 11
437
Первый тестовый пример
Все лазеры уже находятся на разных высотах, поэтому не перекрывают свет друг от друга.
Второй тестовый пример
Изначально все лазеры находятся на одной и той же высоте, поэтому только свет от $$$4$$$-го лазера доходит до экрана.
Можно увеличить расстояние для $$$2$$$-го лазера на $$$1$$$ и расстояние для $$$3$$$-го лазера на $$$2$$$ — в таком случае лазеры будут висеть на расстояниях $$$[1, 2, 3, 1]$$$.
Всего операций изменения будет совершено $$$3$$$ (доступно $$$5$$$), и свет от $$$3$$$ лазеров доходит до экрана.
Обратите внимание, что с помощью $$$5$$$ доступных операций никак нельзя сделать, чтобы все $$$4$$$ лазера висели на различной высоте.
Третий тестовый пример
Один из лазеров на расстоянии $$$5$$$ можно переместить на $$$1$$$ — в таком случае до экрана будет доходить свет от $$$7$$$ различных лазеров.
Обратите внимание, что расстояние от потолка нельзя уменьшать — вы не можете переместить один из лазеров на расстоянии $$$3$$$ на $$$1$$$ ближе к потолку (чтобы его новое расстояние равнялось $$$2$$$).
