Sequência

O professor da importante disciplina de Indução Matemática está tentando resolver uma versão generalizada de um problema muito tradicional: encontrar o valor máximo possível para a soma dos elementos de uma subsequência contígua de uma sequência de números inteiros quaisquer. Mais rigorosamente, dado uma sequência $S = [s_1, s_2 , \ldots, s_N]$, onde $s_i$ é um número inteiro qualquer, para $1 \leq i \leq N$, maximizar $\mathrm{soma}(i, j) = s_i + s_{i+1} + \ldots + s_j$ entre todos os possíveis pares $(i, j)$, onde $1 \leq i \leq j \leq N$.

Na versão do professor, entretanto, alguns elementos da sequência são especiais e estão marcados. Além da sequência marcada, são dadas como entrada duas cotas: $L$ e $H$, com $L \leq H$. O objetivo agora é encontrar o valor máximo possível para a soma dos elementos de uma subsequência contígua, que contenha pelo menos L e no máximo H elementos marcados.

Por definição, uma subsequência vazia (de zero elementos) tem soma igual a zero. Mas note que, como podemos ter uma cota inferior para o número de elementos marcados, a subsequência contígua de soma máxima pode ter soma negativa!

Entrada

A primeira linha da entrada contém três inteiros $N$, $L$ e $H$, indicando respectivamente o número de elementos na sequência, a cota inferior $L$ e a cota superior $H$. A segunda linha contém $N$ inteiros $s_i$, para $1 \leq i \leq N$, definindo os elementos da sequência. A terceira linha contém $N$ inteiros $m_i$, para $1 \leq i \leq N$, indicando as marcas. Se o $i$-ésimo elemento está marcado, o valor é $m_i = 1$. Se não estiver marcado, $m_i = 0$.

Saída

Imprima um inteiro, representando o valor máximo possível para a soma dos elementos de uma subsequência contígua, que contenha pelo menos $L$ e no máximo $H$ elementos marcados.

Restrições

• $1 \leq N \leq 10^5$
• $0 \leq L \leq H \leq 20$
• $-10^3 \leq s_i \leq 10^3$, para $1 \leq i \leq N$
• O número de elementos marcados na sequência é maior ou igual a $L$; portanto sempre existe solução.

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $15$ pontos, $N \leq 10^2$.
• Para um conjunto de casos de testes valendo $30$ pontos, $N \leq 10^4$.

Exemplos

Exemplo de entrada 1

14 3 4
9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12
1 0 0 1 0 1 0 0 1 1 0 0 1 1

Exemplo de saída 1

19

Exemplo de entrada 2

14 7 20
9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12
1 0 0 1 0 1 0 0 1 1 0 0 1 1

Exemplo de saída 2

-12

Exemplo de entrada 3

14 5 5
9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12
1 0 0 1 0 1 0 0 1 1 0 0 1 1

Exemplo de saída 3

14

Exemplo de entrada 4

14 0 20
9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12
1 0 0 1 0 1 0 0 1 1 0 0 1 1

Exemplo de saída 4

26