Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

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

Недавно на уроке информатики Нархан проходил скобочные последовательности. После этого он захотел придумать обозначение $k$-особенной скобочной последовательности.

Давайте рассмотрим скобочную последовательность длины $n$, где $n$ - четное. Нархан сперва выбрал для каждого индекса особенная она или нет. Теперь он считает скобочную последовательность $k$-особенной, если на особенных индексах стоят ровно $k$ открывающихся скобок и сама последовательность является правильной скобочной последовательностью.

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

Вам известны числа $n$ и $k$, массив $a_1, a_2, . . . a_n$, а также какие позиции особенные. Помогите Нархану найти среди всех $k$-особенных скобочных последовательностей максимальную возможную красоту, так как эта задача для него является непосильной.

Определение правильной скобочной последовательности смотрите в примечаниях.

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

Первая строка содержит два целых числа - $n$ и $k$ $(2 \leq n \leq 200000 , 0 \leq k \leq n)$. Гарантируется, что $n$ - четное.

Во второй строке $n$ целых числа $a_1, . . . , a_n$ $(1 \leq a_i \leq 1000000000)$ - значения элементов массива.

В третьей строке $n$ чисел $c_1, . . . , 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