Свинка дает Черепахе три последовательности \(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\) путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Выведите единственное целое число — максимальное значение \(\sum\limits_{i = 1}^m c_{p_i}\). Если невозможно выбрать подпоследовательность длины \(m\), которая удовлетворяет вышеуказанным условиям, выведите \(-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\), которая удовлетворяет обоим условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
2 3 4 2
1 3 3 2
1 4 2 3
|
5
|
|
2
|
7 3
1 4 5 2 3 6 7
1 2 2 1 1 3 2
1 5 6 7 3 2 4
|
13
|
|
3
|
5 3
1 2 3 4 5
1 1 2 1 2
5 4 3 2 1
|
-1
|