F. Пылающее Пламя
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы получили нового ограниченного персонажа события Шилонен. Вы решаете использовать её в бою.

На линии находится $$$n$$$ врагов. $$$i$$$-й враг слева имеет здоровье $$$h_i$$$ и в данный момент находится на позиции $$$x_i$$$. У Шилонен есть урон от атаки $$$m$$$, и вы готовы победить врагов с её помощью.

У Шилонен есть мощная атака «удар по земле». Перед тем, как вы выполните какие-либо атаки, вы выбираете целое число $$$p$$$ и размещаете Шилонен там ($$$p$$$ может быть любой целой позицией, включая позицию с врагом в данный момент). После этого, за каждую атаку она наносит $$$m$$$ урона врагу на позиции $$$p$$$ (если таковой имеется), $$$m-1$$$ урона врагам на позициях $$$p-1$$$ и $$$p+1$$$, $$$m-2$$$ урона врагам на позициях $$$p-2$$$ и $$$p+2$$$, и так далее. Враги, находящиеся на расстоянии не менее $$$m$$$ от Шилонен, не получают урона от атак.

Формально, если враг находится на позиции $$$x$$$, она нанесет $$$\max(0,m - |p - x|)$$$ урона этому врагу за каждую атаку. Обратите внимание, что вы не можете выбрать другое $$$p$$$ для разных атак.

Среди всех возможных $$$p$$$ выведите минимальное количество атак, которые Шилонен должна выполнить, чтобы победить как минимум $$$k$$$ врагов. Если невозможно найти $$$p$$$, при котором в конечном итоге будет побеждено как минимум $$$k$$$ врагов, выведите $$$-1$$$ вместо этого. Обратите внимание, что враг считается побежденным, если его здоровье достигает $$$0$$$ или ниже.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, ..., h_n$$$ ($$$1 \leq h_i \leq 10^9$$$).

Последняя строка каждого набора содержит $$$n$$$ целых чисел $$$x_1, x_2, ..., x_n$$$ ($$$1\leq x_i \leq 10^9$$$, $$$x_i < x_{i+1}$$$ для всех $$$1 \leq i < n$$$)

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

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

Для каждого набора входных данных выведите целое число на новой строке, минимальное количество атак, которые должны быть выполнены, чтобы победить как минимум $$$k$$$ врагов. Если невозможно найти $$$p$$$, при котором в конечном итоге будет побеждено как минимум $$$k$$$ врагов, выведите $$$-1$$$ вместо этого.

Пример
Входные данные
6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3
Выходные данные
2
2
-1
6969697
15
1000000000
Примечание

В первом примере оптимально выбрать $$$p=2$$$. За каждую атаку первый враг получает $$$5-|2-1|=4$$$ урона, второй враг получает $$$5$$$ урона, третий враг получает $$$4$$$ урона, четвертый враг получает $$$3$$$ урона, а пятый враг получает $$$2$$$ урона. После $$$2$$$ атак первые три врага будут побеждены. Можно показать, что невозможно победить $$$3$$$ врага менее чем за $$$2$$$ атаки, независимо от выбранного $$$p$$$.

Во втором примере мы должны убить всех $$$9$$$ врагов. Выбрав $$$p=5$$$, все девять врагов будут побеждены за $$$2$$$ атаки.

В третьем примере мы должны убить обоих врагов. Однако можно показать, что ни одно выбранное $$$p$$$ не повредит обоих врагов одновременно, поэтому ответ будет $$$-1$$$.

В четвертом примере выбор $$$p=1$$$ позволит нам победить первого врага за $$$6969697$$$ атак.

В пятом примере выбор $$$p=10$$$ заставит каждого врага получать $$$1$$$ урон за атаку. Оба врага будут побеждены за $$$15$$$ атак.