D1. Горячий запуск (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие между версиями заключается в ограничениях на $$$t$$$, $$$n$$$, $$$k$$$.

У вас есть компьютер с двумя CPU. Также есть $$$k$$$ программ, пронумерованных целыми числами от $$$1$$$ до $$$k$$$, которые вы можете исполнять на компьютере, каждую только на одном CPU.

$$$i$$$-я программа ($$$1 \le i \le k$$$) занимает $$$cold_i$$$ секунд, чтобы быть исполненной на любом CPU. Однако, если последняя программа, которая исполнялась на этом CPU была также программа $$$i$$$, исполнение занимает $$$hot_i$$$ секунд ($$$hot_i \le cold_i$$$). Обратите внимание, что это выполняется, только если мы исполнили программу $$$i$$$ несколько раз последовательно на этом CPU  — если мы исполняем программу $$$i$$$, потому другую программу, потом программу $$$i$$$, время исполнения программы во второй раз займет $$$cold_i$$$ секунд.

Вам дана последовательность $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, состоящая из целых чисел от $$$1$$$ до $$$k$$$. Вам нужно исполнить на компьютере программы $$$a_1, a_2, \ldots, a_n$$$ в этом порядке. Для всех $$$2 \le i \le n$$$, вы не можете начать исполнять программу $$$a_i$$$, пока программа $$$a_{i - 1}$$$ не завершилась.

Найдите минимальное количество времени нужное, чтобы исполнить все программы $$$a_1, a_2, \ldots, a_n$$$ в таком порядке.

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

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

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

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le k$$$).

В третьей строке каждого набора входных данных находится $$$k$$$ целых чисел $$$cold_1, cold_2, \ldots, cold_k$$$ ($$$1 \le cold_i \le 10^9$$$).

В четвертой строке каждого набора входных данных находится $$$k$$$ целых чисел $$$hot_1, hot_2, \ldots, hot_k$$$ ($$$1 \le hot_i \le cold_i$$$).

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

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

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

Пример
Входные данные
9
3 2
1 2 2
3 2
2 1
4 2
1 2 1 2
5 3
2 1
4 3
1 2 3 1
100 100 100
1 1 1
5 2
2 1 2 1 1
65 45
54 7
5 3
1 3 2 1 2
2 2 2
1 1 1
5 1
1 1 1 1 1
1000000000
999999999
5 6
1 6 1 4 1
3 6 4 1 4 5
1 1 1 1 4 1
1 3
3
4 5 6
1 2 3
8 3
3 3 3 1 2 3 2 1
10 10 8
10 10 5
Выходные данные
6
11
301
225
8
4999999996
11
6
63
Примечание

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

  • Исполнить программу $$$a_1 = 1$$$ на CPU $$$1$$$. Это займет $$$cold_1 = 3$$$ секунды.
  • Исполнить программу $$$a_2 = 2$$$ на CPU $$$2$$$. Это займет $$$cold_2 = 2$$$ секунды.
  • Исполнить программу $$$a_3 = 2$$$ на CPU $$$2$$$. Последняя программа, которая была исполнена на этом CPU была тоже программа $$$2$$$, поэтому это займет $$$hot_2 = 1$$$ секунду.

Суммарно нам потребуется $$$3 + 2 + 1 = 6$$$ секунд, чтобы исполнить все программы. Можно показать, что это оптимальное время.

Во втором наборе входных данных мы можем сделать следующее:

  • Исполнить программу $$$a_1 = 1$$$ на CPU $$$1$$$. Это займет $$$cold_1 = 5$$$ секунд.
  • Исполнить программу $$$a_2 = 2$$$ на CPU $$$2$$$. Это займет $$$cold_2 = 3$$$ секунды.
  • Исполнить программу $$$a_3 = 1$$$ на CPU $$$1$$$. Последняя программа, которая была исполнена на этом CPU была тоже программа $$$1$$$, поэтому это займет $$$hot_1 = 2$$$ секунды.
  • Исполнить программу $$$a_4 = 2$$$ on CPU $$$2$$$. Последняя программа, которая была исполнена на этом CPU была тоже программа $$$2$$$, поэтому это займет $$$hot_2 = 1$$$ секунду.

Суммарно нам потребуется $$$5 + 3 + 2 + 1 = 11$$$ секунд, чтобы исполнить все программы. Можно показать, что это оптимальное время.