A. Шлемы в светлой ночи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пак Чанек — староста деревни Кхунтиен. В одну из ночей, наполненную светом, Пак Чанек неожиданно получил важное объявление, которое необходимо сообщить всем $$$n$$$ жителям Кхунтиена.

Сначала Пак Чанек передает объявление непосредственно одному или нескольким жителям, заплатив $$$p$$$ за каждого человека. После этого жители могут передать объявление другим жителям с помощью волшебного устройства в виде шлема. Однако за использование шлема придется заплатить. Для каждого $$$i$$$, если $$$i$$$-й житель хотя бы раз получал объявление (либо непосредственно от Пак Чанека, либо от другого жителя), то он может передать его не более чем $$$a_i$$$ другим жителям, заплатив $$$b_i$$$ за каждую передачу.

Если Пак Чанек может также контролировать, как жители передают объявление другим жителям, то какова минимальная стоимость того, чтобы Пак Чанек оповестил всех $$$n$$$ жителей Кхунтиена об объявлении?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$p$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq p \leq 10^5$$$) — количество жителей и стоимость того, чтобы Пак Чанек передал объявление непосредственно одному жителю.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq10^5$$$) — максимальное количество жителей, которым каждый житель может передать объявление.

Третья строка каждого набора содержит $$$n$$$ целых чисел $$$b_1,b_2,b_3,\ldots,b_n$$$ ($$$1\leq b_i\leq10^5$$$) — стоимость передачи объявления одним жителем другому.

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

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

Для каждого набора входных данных выведите в отдельной строке минимальную стоимость уведомления всех $$$n$$$ жителей Хунтина об объявлении.

Пример
Входные данные
3
6 3
2 3 2 1 1 3
4 3 2 6 3 6
1 100000
100000
1
4 94
1 4 2 3
103 96 86 57
Выходные данные
16
100000
265
Примечание

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

  1. Пак Чанек передает объявление непосредственно $$$3$$$-му, $$$5$$$-му и $$$6$$$-му жителю. Это требует затрат в размере $$$p+p+p=3+3+3=9$$$.
  2. Житель $$$3$$$ передает сообщение жителям $$$1$$$ и $$$2$$$. Это требует затрат в размере $$$b_3+b_3=2+2=4$$$.
  3. $$$2$$$-й житель передает объявление $$$4$$$-му. Это требует затрат $$$b_2=3$$$.

Общая стоимость составляет $$$9+4+3=16$$$. Можно показать, что не существует стратегии с меньшими затратами.