uCoder | 1178 | Nível: 5 | Tempo Limite: 10
Quadro Premiado
Adaptado por erich.rodriguesf
Você está em um programa de televisão, e tem uma ótima chance de ganhar muito dinheiro. Trata-se de um jogo com algumas regras peculiares, e o montante de dinheiro resultante dependerá apenas da sua esperteza, podendo-se até sair perdendo caso se jogue mal.
O jogo funciona da seguinte maneira: há um quadro, com N linhas e M colunas, e em cada posição deste quadro há um inteiro positivo, representando uma quantia em dinheiro. Em cada uma dessas posições você tem a opção de colocar um dos seguintes sinais:
'+' - Significa que o valor daquela posição deve ser somado à seu prêmio.
'-' - Significa que o valor daquela posição deve ser subtraído do seu prêmio.
'.' - Significa que tal posição deve ser ignorada.
A vida seria muito simples se você pudesse colocar '+' em todas as posições, portanto há duas regras adicionais ao jogo: para cada linha do quadro, você deve preencher as posições com um dos padrões de sinais montados pelos organizadores do jogo; e para cada coluna do quadro, não é permitido que duas posições adjacentes verticalmente tenham o mesmo sinal (se aplica aos sinais '+' e '-'). É possível usar o mesmo padrão mais de uma vez, desde que não desrespeitando a segunda
regra acima.
Veja um exemplo na imagem abaixo, onde os padrões são: “++”, “--”, “.+” e “+.”.
Considere que há sempre ao menos uma maneira de se completar o quadro.
Como o jogo é novo, eles deixaram que você usasse seu computador para te ajudar na decisão, sem saber que você era um programador. Escreva um algoritmo que lhe diga qual a soma máxima que é possível alcançar no jogo.
Entrada
Haverá diversos casos de teste. Cada caso de teste inicia com dois inteiros, N e M (1 ≤ N, M ≤ 100), indicando o número de linhas e de colunas do quadro, respectivamente.
A seguir haverá N linhas, contendo M inteiros cada, representando os valores do quadro. Seja v o valor de qualquer posição do quadro, 1 ≤ v ≤ 100.
A seguir haverá um inteiro K, indicando o número de padrões. Em seguida haverá K (1 ≤ K ≤ 100) linhas, cada uma com M caracteres, representando cada um dos padrões, conforme a simbologia descrita no enunciado.
O último caso de teste é indicado quando N = M = 0, o qual não deverá ser processado.
Saída
Para cada caso de teste imprima uma linha, contendo um inteiro, representando a soma máxima que é possível alcançar se os padrões forem escolhidos de forma ótima.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
2 2 |
5 |