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

ЕсепF. Нархан және жақшалар

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

1.5 seconds

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

256 megabytes

Нархан информатика сабағында жақшалар тізбегін өтті. Осыдан кейін, оған керемет ой келді: $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$-индекс ерекше екенін білдіреді, әйтпесе жоқ.

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

Ұзындығы $n$ болатын $k$-ерекше жақшалар тізбегі болмаса, $-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 )