C. Монстры и заклинания
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп снова играет в компьютерную игру. Он ученик мага, поэтому знает только одно заклинание. К счастью, это заклинание может наносить урон монстрам.

Уровень, на котором он сейчас, содержит $$$n$$$ монстров. $$$i$$$-й из них появляется через $$$k_i$$$ секунд с начала уровня и имеет $$$h_i$$$ очков здоровья. Дополнительно есть ограничение $$$h_i \le k_i$$$ для всех $$$1 \le i \le n$$$. Все $$$k_i$$$ различны.

Монокарп может использовать заклинание в моменты времени, которые являются положительным целым количеством секунд с начала уровня: $$$1, 2, 3, \dots$$$ Урон от заклинания считается следующим образом. Если он не использовал заклинание в предыдущую секунду, то урон равен $$$1$$$. Иначе, пусть урон в прошлую секунду был равен $$$x$$$. Тогда он может выбрать, чтобы урон был либо $$$x + 1$$$, либо $$$1$$$. Заклинание использует ману: использование заклинания с уроном $$$x$$$ использует $$$x$$$ маны. Мана не восстанавливается.

Чтобы убить $$$i$$$-го монстра, Монокарп должен использовать заклинание с уроном хотя бы $$$h_i$$$ ровно в тот момент, когда появляется монстр, что равно $$$k_i$$$.

Обратите внимание, что Монокарп может использовать заклинание и тогда, когда в текущую секунду монстра нет.

Количество маны, необходимое для использования всех заклинаний, — это сумма маны по всем использованным заклинаниям. Посчитайте наименьшее количество маны, которое потребуется Монокарпу, чтобы убить всех монстров.

Можно показать, что всегда можно убить всех монстров в рамках ограничений задачи.

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество монстров на уровне.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$k_1 < k_2 < \dots < k_n$$$ ($$$1 \le k_i \le 10^9$$$) — количество секунд с начала уровня до появления $$$i$$$-го монстра. Все $$$k_i$$$ различны, $$$k_i$$$ заданы в порядке возрастания.

В третьей строке записаны $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le k_i \le 10^9$$$) — здоровье $$$i$$$-го монстра.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

На каждый набор входных данных выведите одно целое число — наименьшее количество маны, которое потребуется Монокарпу, чтобы убить всех монстров.

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

В первом наборе входных данных Монокарп может использовать заклинание через $$$3, 4, 5$$$ и $$$6$$$ секунд с начала уровня с уроном $$$1, 2, 3$$$ и $$$4$$$, соответственно. Урон в $$$6$$$ секунду равен $$$4$$$, что действительно больше или равно здоровью монстра, который появляется.

Во втором наборе входных данных Монокарп может использовать заклинание через $$$3, 4$$$ и $$$5$$$ секунд с начала уровня с уроном $$$1, 2$$$ и $$$3$$$, соответственно.

В третьем наборе входных данных Монокарп может использовать заклинание через $$$4, 5, 7, 8$$$ и $$$9$$$ секунд с начала уровня с уроном $$$1, 2, 1, 1$$$ и $$$2$$$, соответственно.