4-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача F. Нархан и скобочки

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

Недавно на уроке информатики Нархан проходил скобочные последовательности. После этого он захотел придумать обозначение $k$-особенной скобочной последовательности. Давайте рассмотрим скобочную последовательность длины $n$, где $n$ - четное. Нархан сперва выбрал для каждого индекса особенная она или нет. Теперь он считает скобочную последовательность $k$-особенной, если на особенных индексах стоят ровно $k$ открывающихся скобок и сама последовательность является правильной скобочной последовательностью. Также он хочет определить красоту этой скобочной последовательности и для этого у него есть массив из $n$ положительных целых чисел $a_1, a_2, \dots a_n$. Давайте выпишем все индексы $k$-особенной скобочной последовательности где стоят открывающиеся скобки, пусть это $i_1, i_2, \dots, i_m$. Тогда красотой этой последовательности для Нархана будет - $a_{i_1} + a_{i_2} + \dots + a_{i_m}$. Вам известны числа $n$ и $k$, массив $a_1, a_2, \dots a_n$, а также какие позиции особенные. Помогите Нархану найти среди всех $k$-особенных скобочных последовательностей максимальную возможную красоту, так как эта задача для него является непосильной. Определение правильной скобочной последовательности смотрите в примечаниях.

Формат входного файла

Первая строка содержит два целых числа - $n$ и $k$ ($2 <= n <= 2*10^5, 0 <= k <= n$) . Гарантируется, что $n$ - четное. Во второй строке $n$ целых числа $a_1, \ldots, a_n$ ($1 <= a_i <= 10^9$) - значения элементов массива. В третьей строке $n$ чисел $c_1, \ldots, c_n$ $(c_i = \{0, 1\})$. $c_i=1$ означает, что индекс $i$ - особенный, иначе нет.

Формат выходного файла

Если нет ни одной $k$-особенной скобочной последовательности длины $n$ выведите $-1$. Иначе выведите максимальную красоту среди всех $k$-особенных скобочных последовательностей

Примеры:

Вход

6 3
1 6 3 4 7 3
1 1 1 1 1 1

Ответ

14

Вход

6 0
1 2 3 4 5 6
1 0 0 0 0 0

Ответ

-1

Вход

8 3
7 9 12 5 6 6 8 9
0 1 1 0 1 1 1 0

Ответ

36

Замечание

Напомним, что такое правильная скобочная последовательность:

• <<()>> — правильная скобочная последовательность;
• если $s$ — правильная скобочная последовательность, то <<(>> + $s$ + <<)>> — правильная скобочная последовательность;
• если $s$ и $t$ — правильные скобочные последовательности, то $s + t$ — правильная скобочная последовательность.

Например, <<()()>>, <<(())()>>, <<(())>> и <<()>> являются правильными скобочными последовательностями, а <<)(>>, <<()(>> и <<)))>> — нет. ( Narkhan Kamzabek )