D. Гений
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
32 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на нестандартное ограничение по памяти.

Есть $$$n$$$ задач, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. У $$$i$$$-й задачи есть сложность $$$c_i = 2^i$$$, тэг $$$tag_i$$$ и счёт $$$s_i$$$.

После задачи с номером $$$i$$$ можно решить задачу с номером $$$j$$$ только в том случае, если $$$\text{IQ} < |c_i - c_j|$$$ и $$$tag_i \neq tag_j$$$. После этого $$$\text{IQ}$$$ меняется и становится равным $$$\text{IQ} = |c_i - c_j|$$$ и вы набираете $$$|s_i - s_j|$$$ очков.

Первой можно решить любую задачу. Задачи можно решать в любом порядке, каждую сколько угодно раз.

Изначально $$$\text{IQ} = 0$$$. Найдите максимальное количество очков, которое можно набрать.

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

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

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

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$tag_1, tag_2, \ldots, tag_n$$$ $$$(1 \le tag_i \le n)$$$  — тэги задач.

В третьей строке описания каждого набора входных данных находятся $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \le s_i \le 10^9)$$$  — счёт задач.

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

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

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

Пример
Входные данные
5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666
Выходные данные
35
30
42
0
0
Примечание

В первом наборе входных данных оптимальная последовательность решения задач такая:

  1. $$$1 \rightarrow 2$$$, после этого суммарный счёт равен $$$5$$$ и $$$\text{IQ} = 2$$$
  2. $$$2 \rightarrow 3$$$, после этого суммарный счёт равен $$$10$$$ и $$$\text{IQ} = 4$$$
  3. $$$3 \rightarrow 1$$$, после этого суммарный счёт равен $$$20$$$ и $$$\text{IQ} = 6$$$
  4. $$$1 \rightarrow 4$$$, после этого суммарный счёт равен $$$35$$$ и $$$\text{IQ} = 14$$$

Во втором наборе входных данных оптимальная последовательность решения задач такая:

  1. $$$1 \rightarrow 2$$$, после этого суммарный счёт равен $$$5$$$ и $$$\text{IQ} = 2$$$
  2. $$$2 \rightarrow 3$$$, после этого суммарный счёт равен $$$10$$$ и $$$\text{IQ} = 4$$$
  3. $$$3 \rightarrow 4$$$, после этого суммарный счёт равен $$$15$$$ и $$$\text{IQ} = 8$$$
  4. $$$4 \rightarrow 1$$$, после этого суммарный счёт равен $$$35$$$ и $$$\text{IQ} = 14$$$

В третьем наборе входных данных оптимальная последовательность решения задач такая:

  1. $$$1 \rightarrow 3$$$, после этого суммарный счёт равен $$$17$$$ и $$$\text{IQ} = 6$$$
  2. $$$3 \rightarrow 4$$$, после этого суммарный счёт равен $$$35$$$ и $$$\text{IQ} = 8$$$
  3. $$$4 \rightarrow 2$$$, после этого суммарный счёт равен $$$42$$$ и $$$\text{IQ} = 12$$$