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₁,s₂,...,s_N], onde s_i é um número inteiro qualquer, para 1 ≤ i ≤ N, maximizar soma(i,j)=s_i+s_i+1+...+s_j entre todos os possíveis pares (i,j), onde 1 ≤ i ≤ j ≤ 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 ≤ 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 ≤ i ≤ N, definindo os elementos da sequência. A terceira linha contém N inteiros m_i, para 1 ≤ i ≤ 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 uma única linha contendo 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 ≤ N ≤ 10⁵
• 0 ≤ L ≤ H ≤ 20
• -10³ ≤ s_i ≤ 10³, para 1 ≤ i ≤ 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 ≤ 10²
• Para um conjunto de casos de testes valendo 30 pontos, N ≤ 10⁴

Exemplos

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

19
	

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

-12
	

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

14
	

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

26