F. Черепаха и три последовательности
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Свинка дает Черепахе три последовательности $$$a_1, a_2, \ldots, a_n$$$, $$$b_1, b_2, \ldots, b_n$$$ и $$$c_1, c_2, \ldots, c_n$$$.

Черепаха выберет подпоследовательность из $$$1, 2, \ldots, n$$$ длины $$$m$$$, пусть это будет $$$p_1, p_2, \ldots, p_m$$$. Подпоследовательность должна удовлетворять следующим условиям:

  • $$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_m}$$$;
  • Все $$$b_{p_i}$$$ для всех индексов $$$i$$$ попарно различны, т.е. не существует двух различных индексов $$$i$$$, $$$j$$$, таких что $$$b_{p_i} = b_{p_j}$$$.

Помогите ему найти максимальное значение $$$\sum\limits_{i = 1}^m c_{p_i}$$$, или скажите ему, что невозможно выбрать подпоследовательность длины $$$m$$$, которая удовлетворяет вышеуказанным условиям.

Напомним, что последовательность $$$a$$$ является подпоследовательностью последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ путем удаления нескольких (возможно, нуля или всех) элементов.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3000$$$, $$$1 \le m \le 5$$$) — длины трех последовательностей и требуемая длина подпоследовательности.

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

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — элементы последовательности $$$b$$$.

Четвертая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^4$$$) — элементы последовательности $$$c$$$.

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

Выведите единственное целое число — максимальное значение $$$\sum\limits_{i = 1}^m c_{p_i}$$$. Если невозможно выбрать подпоследовательность длины $$$m$$$, которая удовлетворяет вышеуказанным условиям, выведите $$$-1$$$.

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

В первом тесте мы можем выбрать $$$p = [1, 2]$$$, тогда $$$c_{p_1} + c_{p_2} = 1 + 4 = 5$$$. Мы не можем выбрать $$$p = [2, 4]$$$, так как $$$a_2 > a_4$$$, что нарушает первое условие. Мы также не можем выбрать $$$p = [2, 3]$$$, так как $$$b_2 = b_3$$$, что нарушает второе условие. Мы можем выбрать $$$p = [1, 4]$$$, но $$$c_1 + c_4 = 4$$$, что не является максимальным.

Во втором тесте мы можем выбрать $$$p = [4, 6, 7]$$$.

В третьем тесте невозможно выбрать подпоследовательность длины $$$3$$$, которая удовлетворяет обоим условиям.