Problema H: Zega Zinga, Zoga Zonga


image zzzzFig
Zega Zinga: Huummm... Onze.
Zoga Zonga: Doze!

Zega Zinga: Onze!
Zoga Zonga: Não! Doze!

Zega Zinga: A zério?
Zoga Zonga: Zim. Doze.

Zega Zinga: Zurpreendente! Como zegazte tão deprezza à zoluzão?

Zega Zinga e Zoga Zonga, abelhas de alta competição, têm um problema: o campo de treino dos Bem-me-queres floridos, onde diariamente saciam o seu apetite, foi tomado pelas Vespas. Por isso, atravessar o campo requer agora outros cuidados. Quais? Escolher a flor de partida no lado do campo onde se encontram. Escolher como próxima flor uma das três vizinhas imediatamente à frente (nunca flores ao seu lado ou atrás). Repetir até chegar ao outro lado do campo, sem se esquecerem de recolher o néctar, claro. As Vespas? Certo. Convém evitar as Vespas disfarçadas de flor.

Podem ajudar Zega Zinga a calcular a maior quantidade de néctar que pode recolher numa travessia do campo, evitando, obviamente, as Vespas?

Tarefa

As flores do campo dos Bem-me-queres floridos estão dispostas numa grelha retangular. Uma descrição do campo especifica, para cada flor, a quantidade de néctar presente na flor ou se está uma Vespa pousada na flor.

Escreva um programa que, dada uma descrição do campo, indique a maior quantidade de néctar que pode ser recolhida pela abelha Zega Zinga numa travessia do campo (ou seja, num caminho do topo até à base do campo). Poderá ser escolhida como flor de partida qualquer uma das pertencentes à linha do topo (que corresponde à primeira linha), desde que não tenha Vespa. A deslocação terá de ser sempre entre flores vizinhas entre si, podendo ser utilizada uma única flor por cada linha. Flores com Vespas não podem fazer parte do caminho. Caso não exista nenhum caminho que atravesse o campo de um lado ao outro (que comece na primeira linha e termine na última linha), devido à presença de Vespas, deverá ser escrito o valor zero.

Input

A primeira linha do input contém dois inteiros, L e C, que representam, respetivamente, o número de linhas e o número de colunas da grelha de flores que descreve o campo. Seguem-se L linhas, cada uma com C elementos, separados por um espaço. Cada elemento é:
  • a letra "V", caso se trate de uma flor com uma Vespa;
  • um inteiro N, que corresponde à quantidade de néctar da flor, caso a flor esteja livre de Vespas.

Restrições

  1≤L≤100 Número de linhas do campo
  1≤C≤100 Número de colunas do campo
  0≤N≤100 Quantidade de néctar de uma flor

Output

O output tem uma única linha com:
  • um inteiro que representa a maior quantidade de néctar que pode ser recolhida pela abelha Zega Zinga numa travessia do campo (ou seja, num caminho da primeira até à última linha do campo);
  • "0" (zero), se não existir um caminho da primeira até à última linha do campo (conforme definido acima), devido à presença de Vespas.

Exemplo 1

Input 

3 4
5 2 3 1
1 1 1 4
5 2 5 2

Output 

12

Explicação

Zega Zinga pode recolher
3 unidades de néctar na primeira linha,
4 unidades na segunda linha e
5 unidades na terceira linha.

Exemplo 2

Input 

3 4
5 2 3 1
1 1 V V
5 2 5 15

Output 

11

Explicação

Zega Zinga pode recolher
5 unidades de néctar na primeira linha,
1 unidade na segunda linha e
5 unidades na terceira linha.
Tem várias maneiras de o fazer.

Exemplo 3

Input 

3 4
5 2 V V
V V V 4
5 2 5 15

Output 

0

Explicação

Zega Zinga não consegue atravessar o campo, devido às Vespas.


ToPAS'2024