e-olymp
Yarışlar

ACM-ICPC, SEERC, 1/4 2019-2020

Козак Вус 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].

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
7 3
3 1 3 3 2 2 1
12 10 1
Çıxış verilənləri #1
22
Giriş verilənləri #2
7 5
1 3 5 1 2 4 2
18 18 14 10 1
Çıxış verilənləri #2
61
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019