Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RTURCA - Roleta turca

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 Xi, 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 Yi, 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


Adicionado por:Wanderley Guimarăes
Data:2008-12-27
Tempo limite:0.371s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.