e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
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