Козак Вус i нова гра#9097
Козак Вус нарешті придумав свою першу гру, але ще нікому її не показував. Він просить вас протестувати цю гру.
Вам дано масив довжини . Також дано число . Всі числа масиву — цілі додатні числа, що не перевищують . У кожного числа від до є своя ціна. Щоб виграти гру, треба знайти підвідрізок масиву з максимальною ціною. Ціна підвідрізка — це сума цін чисел, які зустрічаються на підвідрізку рівно раз.
Допоможіть Козакові знайти для заданих масиву та цін чисел максимальну ціну підвідрізка.
Перший рядок містить два цілі числа та (1 \leq m \leq n \leq 200\,000) — розмір масиву та максимальне число у масиві.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq m) — числа масиву. Гарантується, що кожне число від до зустрічається хоча б один раз.
Третій рядок містить цілих чисел c_1, c_2, \ldots, c_m (1 \leq c_i \leq 1\,000\,000) — ціни чисел.
В єдиному рядку виведіть одне число — відповідь на задачу.
Приклад 1
Приклад 2
У першому прикладі підвідрізок з максимальною ціною — [6\,\ldots\,7].
У другому прикладі підвідрізок з максимальною ціною — [2\,\ldots\,6].