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

У Мухаммада Али есть целочисленный массив $$$a_1,\dots,a_n$$$. Он может изменить (заменить) любое подмножество позиций; изменение позиции $$$i$$$ стоит $$$c_i$$$ и замену $$$a_i$$$ на любое целое число по его выбору. Позиции, которые он не меняет, должны сохранять свои исходные значения.

После всех изменений назовём спадом индекс $$$i$$$ ($$$1 \le i \lt n$$$), для которого итоговое значение на позиции $$$i$$$ строго больше итогового значения на позиции $$$i+1$$$. Мухаммад Али хочет, чтобы итоговый массив не содержал спадов.

Найдите минимальную стоимость изменений, необходимую, чтобы в массиве не было спадов.

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

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

Каждый набор входных данных состоит из трёх строк:

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 8000$$$) — длину массивов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.

Третья строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — стоимости изменений.

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

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

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

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

В первом и втором примерах массив уже не имеет спадов, так что изменять элементы не нужно.

В третьем примере из оптимальных массивов: $$$[2,3,5,6]$$$, для его получения нужно заменить все элементы, кроме второго, так что ответ равен $$$c_1 + c_3 + c_4 = 3$$$.