Козак Вус i нова гра
Козак Вус i нова гра
Козак Вус нарештi придумав свою першу гру, але ще нiкому її не показував. Вiн просить вас протестувати цю гру.
Вам дано масив a довжини n. Також дано число m. Всi числа масиву — цiлi додатнi числа, що не перевищують m. У кожного числа вiд 1 до m є своя цiна. Щоб виграти гру, треба знайти пiдвiдрiзок масиву з максимальною цiною. Цiна пiдвiдрiзка — це сума цiн чисел, якi зустрiчаються на пiдвiдрiзку рiвно 1 раз.
Допоможiть Козаковi знайти для заданих масиву та цiн чисел максимальну цiну пiдвiдрiзка.
Формат вхiдних даних
Перший рядок мiстить два цiлi числа n та m (**1 ≤ m ≤ n ≤ 200 000**) — розмiр масиву та максимальне число у масивi.
Другий рядок мiстить n цiлих чисел a1
, a2
, . . . , an
(**1 ≤ ai
≤ m**) — числа масиву. Гарантується, що кожне число вiд 1 до m зустрiчається хоча б один раз.
Третiй рядок мiстить m цiлих чисел c1
, c2
, . . . , cm
(**1 ≤ ci
≤ 1 000 000**) — цiни чисел.
Формат вихiдних даних
В єдиному рядку виведiть одне число — вiдповiдь на задачу.
Примiтка
У першому прикладi вiдрiзок з максимальною цiною — [6 . . . 7].
У другому прикладi вiдрiзок з максимальною цiною — [2 . . . 6].
7 3 3 1 3 3 2 2 1 12 10 1
22
7 5 1 3 5 1 2 4 2 18 18 14 10 1
61