G. Дорожные работы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В строящейся деревне в один ряд построены $$$n$$$ домов, пронумерованных от $$$1$$$ до $$$n$$$. Дом $$$i$$$ обладает гостеприимством $$$h_i$$$.

В деревне запланировано $$$n - 1$$$ дорог, где дорога $$$i$$$ соединяет дома $$$i$$$ и $$$i + 1$$$ и будет построена в день $$$d_i$$$. Изначально ни одна дорога не построена.

Вы начинаете в доме $$$x$$$ и проводите в деревне время с $$$1$$$-го по $$$k$$$-й день, изначально имея уровень удовлетворенности $$$0$$$. В каждый день $$$s$$$ по порядку происходит следующее:

  • Строятся все дороги $$$i$$$, у которых $$$d_i = s$$$;
  • Вы можете перейти в соседний дом, если дорога к нему уже построена, или остаться в своем текущем доме;
  • Ваша удовлетворенность увеличивается на $$$h_j$$$, где $$$j$$$ — дом, в котором вы сейчас находитесь.

Найдите максимальную удовлетворенность, которую вы можете получить за $$$k$$$ дней.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$, $$$1 \le x \le n$$$) — количество домов, количество дней и начальный дом соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$0 \le h_i \le 10^9$$$) — гостеприимство каждого дома.

Третья строка содержит $$$n - 1$$$ целых чисел $$$d_1, d_2, \ldots, d_{n - 1}$$$ ($$$1 \le d_i \le k$$$) — день, в который строится каждая из дорог.

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

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

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

Пример
Входные данные
4
5 10 3
14 2 3 5 6
10 6 2 7
4 8 1
0 0 0 1
7 1 2
2 1000000000 1
1 1000000000
1
9 27 6
17 13 5 8 14 3 4 17 20
10 1 2 13 3 15 6 23
Выходные данные
52
0
1000000000000000000
386
Примечание

В первом наборе входных данных одна из оптимальных последовательностей ходов выглядит следующим образом:

  • Вы начинаете в доме $$$x = 3$$$ с удовлетворенностью $$$0$$$.
  • В $$$1$$$-й день дороги еще не построены, поэтому вы вынуждены остаться в доме $$$3$$$. Ваша удовлетворенность становится равной $$$3$$$.
  • На $$$2$$$-й день строится дорога $$$3$$$. Вы переходите в дом $$$4$$$ и остаетесь там в дни $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$ и $$$7$$$. Ваша удовлетворенность становится равной $$$33$$$. За это время также строятся дороги $$$2$$$ и $$$4$$$.
  • На $$$8$$$-й день вы переходите обратно в дом $$$3$$$. Ваша удовлетворенность становится равной $$$36$$$.
  • На $$$9$$$-й день вы переходите в дом $$$2$$$. Ваша удовлетворенность становится равной $$$38$$$.
  • На $$$10$$$-й день строится дорога $$$1$$$. Вы переходите в дом $$$1$$$. Ваша удовлетворенность становится равной $$$52$$$.

Можно показать, что достичь удовлетворенности больше $$$52$$$ невозможно.

Во втором наборе входных данных вы не можете добраться до дома $$$4$$$ за $$$8$$$ дней, поэтому максимальная достижимая удовлетворенность равна $$$0$$$.

В третьем наборе входных данных вы можете сразу же перейти в дом $$$2$$$ и оставаться там на протяжении всех $$$1\,000\,000\,000$$$ дней.