Statement is not available in English language
B. Ночная операция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ночь — самое время расследовать дело о похищении слона. Взяв лишь старый фонарь с зарядом в $$$M$$$ единиц и шляпы, Шеф и Коллега вышли на «охоту».

Поиски слона начнутся с главной улицы. Детективы идут по ней прямо с самого начала без единой остановки, со скоростью $$$1$$$ метр в секунду и постоянно светят вперёд фонариком, длина луча которого равна $$$H$$$ метров.

На расстояниях $$$b_1, b_2, \ldots, b_n$$$ метров от начала улицы стоят зеваки. Считается, что луч фонаря детективов попадает на $$$i$$$-го зеваку, как только сумма позиции детективов от начала улицы и длины луча фонаря становится не меньше $$$b_i$$$.

В момент попадания луча на зеваку он начинает бежать навстречу детективам с ускорением $$$a$$$ метров на секунду в квадрате. Если в момент столкновения зевака имеет скорость $$$V$$$ метров в секунду, придётся отпугнуть его ультрафиолетовой вспышкой, потратив $$$(V+1)^2$$$ единиц заряда фонаря. Обратите внимание, что в другие моменты заряд фонаря не тратится.

Слона в эту ночь братья детективы не нашли, зато к концу «охоты» у фонарика остался строго положительный заряд.

Найдите максимальную целую положительную длину луча $$$H$$$, при которой к концу «охоты» заряд фонаря останется строго положительным.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора даны три целых числа $$$n$$$, $$$a$$$, $$$M$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le a \le 2500$$$, $$$3 \cdot n \cdot a \le M \le 2 \cdot 10^{14}$$$) — количество зевак, ускорение зеваки при приближении к детективам и заряд фонаря.

Во второй строке каждого набора даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \cdot n \le 10^{18}$$$) — позиции зевак от начала улицы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите максимальную подходящую длину луча в метрах.

Гарантируется, что решение существует.

Пример
Входные данные
4
4 1 22
1 2 3 4
4 2 50
2 2 4 7
5 2 30
10 10 10 10 10
3 3 81
4 6 7
Выходные данные
2
3
1
4
Примечание

Рассмотрим первый набор входных данных.

Если $$$H = 2$$$:

  • 1-й зевака стартует в $$$T = 0$$$, врежется со скоростью $$$\sqrt{3} - 1$$$ и снимет $$$3$$$ единицы заряда;
  • 2-й зевака стартует в $$$T = 0$$$, врежется со скоростью $$$\sqrt{5} - 1$$$ и снимет $$$5$$$ единиц заряда;
  • 3-й зевака стартует в $$$T = 1$$$, врежется со скоростью $$$\sqrt{5} - 1$$$ и снимет $$$5$$$ единиц заряда;
  • 4-й зевака стартует в $$$T = 2$$$, врежется со скоростью $$$\sqrt{5} - 1$$$ и снимет $$$5$$$ единиц заряда.

Суммарно зеваки снимут $$$3 + 5 + 5 + 5 = 18$$$ единицы заряда, $$$22 - 18 \gt 0$$$.

Если $$$H = 3$$$:

  • 1-й зевака стартует в $$$T = 0$$$, врежется со скоростью $$$\sqrt{3} - 1$$$ и снимет $$$3$$$ единицы заряда;
  • 2-й зевака стартует в $$$T = 0$$$, врежется со скоростью $$$\sqrt{5} - 1$$$ и снимет $$$5$$$ единиц заряда;
  • 3-й зевака стартует в $$$T = 0$$$, врежется со скоростью $$$\sqrt{7} - 1$$$ и снимет $$$7$$$ единиц заряда;
  • 4-й зевака стартует в $$$T = 1$$$, врежется со скоростью $$$\sqrt{7} - 1$$$ и снимет $$$7$$$ единиц заряда.

Суммарно зеваки снимут $$$3 + 5 + 7 + 7 = 22$$$ единицы заряда, $$$22 - 22 = 0$$$.

Можно показать, что максимальная подходящая длина луча равна двум.

Если вы дочитали примечание до конца, возможно, вам поможет картинка, иллюстрирующая расстояние между детективами и вторым зевакой в разные моменты времени при $$$H = 3$$$: