SPOJ Brasil

Roleta turca é um jogo de azar que usa uma roleta com S espaços, cada um numerado com um inteiro entre -64 e 64. Em cada turno do jogo, os jogadores apostam em B bolas, cada uma também numerada de -64 a 64. Para cada uma das B bolas, exatamente um jogador apostará nela.

Após girar a roleta, o representante da banca joga as B bolas seqüêncialmente. Quando a roleta para, cada bola está disposta em dois espaços adjacentes, como decrito na figura a seguir, que mostra uma roleta com 32 espaços e 4 bolas. Note que, como a figura ilustra, uma bola ocupa dois espaços adjacentes, e, portanto, há espaço para no máximo S / 2 bolas na roleta.

A bolas terminam dispostas na mesma posição relativa em que elas foram jogadas na roleta. Isto é, se as bolas a, b e c são jogadas nessa seqüência, elas terminam dispostas tais que, na direção horária, a é seguida por b que é seguida por c que é seguida por a.

A valor de uma bola em um turno é calculado pela multiplicação do número da bola pela soma dos números dos espaços adjacentes sobre os quais a bola está disposta. Se o valor de uma bola é positivo, o jogador que apostou nessa bola recebe essa quantia (o valor da bola) da banca; se o valor de um bola é negativo, o jogador que apostou nessa bola deve pagar essa quantia para a banca. A arrecadação da banca em um turno é a quantia total recebida menos a quantia total paga.

Por exemplo, na figura anterior, a banca paga $5.00 para bola numerada -1, paga $7.00 para bola numerada -7, recebe $24 pela bola numerada 12 e não paga nem recebe pela bola numerada 3. Portanto, neste turno a banca fez uma arrecadação de $12.00 (24 -5 -7); note que a arrecadação da banca em turno pode ser negativa(perda).

Será dada a descrição da roleta, a descrição das bolas e a seqüência em que as bolas foram jogadas na roleta. Escreva um programa que determine a arrecadação máxima que a banca pode fazer em um turno.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros S e B que indicam respectivamente o número de espaços na roleta (3 <= S <= 250) e o número de bolas usadas (1<=B<=teto(S/2)). A segunda linha de um caso de teste contém S inteiros X_i, indicando os números associados com os espaços da roleta, na direção horária (-64 <= Xi <= 64, para 1 <= i <= S). A terceira linha de um caso de teste contém B inteiros Y_i, indicando o número associado com as bolas (-64 <= Yi <= 64, para 1 <= i<= B), na seqüência em que as bolas são jogadas na roleta (note que elas estão na ordem que elas terminam dispostas na roleta, na direção horária). O fim da entrada é indicada por S=B=0. A entrada deve ser lida da entrada padrão.

Saída

Para cada caso de teste na entrada seu programa deve escrever uma linha de saída, contendo um inteiro indicando a máxima arrecadação que a banca pode obter em um turno. A saída deve ser escrita na saída padrão.

Exemplo de entrada
4 2 
-1 0 2 -1 
-1 1 
5 2 
3 2 -1 7 1 
2 3 
7 3 
-4 3 2 1 0 -4 -2 
-10 0 1 
4 2 
0 2 3 0 
-2 -2 
0 0

Exemplo de saída
4
-11
56
10