SPOJ Brasil

Felipe é um grande fã da série de jogos The Legend of Zelda, criada pela Nintendo. Como um bom fã, comprou todos os jogos que foram lançados até então e atualmente está jogando Zelda: Twilight Princess no seu Wii ao invés de terminar sua dissertação de Mestrado.

Após jogar por dezenas de horas, Felipe ainda não conseguiu passar de um mini game e conquistar o último heart piece que resta. O mini game consiste no seguinte: em um passeio de dragão, Link, o herói do jogo, deve estourar balões e acumular o máximo de pontos possíveis. Existem 3 tipos de balões, possivelmente com valores distintos. Ao estourar o i-ésimo balão, que é do tipo k, a pontuação total aumenta em V_k caso o último balão estourado seja de um tipo diferente do balão i, ou aumenta em o dobro do valor computado no último balão caso ele seja do mesmo tipo que o balão i (isso é considerado um bônus). Porém, esse bônus só pode dobrar de valor no máximo nove vezes, ou seja, o valor máximo que um balão do tipo k pode alcançar é min(dobro do último balão, V_k · 2⁹). Se um balão não for estourado, ele não é contabilizado na soma final. V_k é o valor inicial de todos os balões do tipo k (k ∈ {a,b,c}), representado pelos valores A, B e C da entrada.

Os balões devem ser estourados na ordem em que aparecem, mas é possível decidir entre estourar ou não cada um dos balões para assim tentar aproveitar o bônus acumulado e aumentar a pontuação final. Ajude Felipe a calcular qual a maior pontuação possível de ser obtida no mini game para que ele possa tentar melhorar sua estratégia.

Entrada

A primeira linha da entrada contém um inteiro T, o número de casos de teste, seguido de T*2 linhas. Cada caso de teste é composto por duas linhas. Na primeira linha de cada teste são dados três inteiros A, B e C (1 ≤ A, B, C ≤ 10), os valores iniciais dos três tipos de balões. Na segunda linha do teste é dada uma string S com no mínimo 1 e no máximo 100 caracteres e contendo apenas as letras a, b e c, os tipos dos balões que aparecerão. Inicialmente, balões do tipo a valem A, do tipo b valem B e do tipo c valem C.

Saída

Para cada caso de teste, imprima uma linha contendo a pontuação máxima possível de ser alcançada no jogo, considerando que Felipe é capaz de estourar todos os balões mas respeitando a ordem dada em S.

Exemplos

Entrada:
2
1 2 4
acb
2 5 3
acaa

Saída:
7
14

No primeiro caso, o melhor a fazer é estourar todos os balões.

No segundo caso, o ideal é não estourar o segundo balão, de forma que o primeiro balão valerá 2, o terceiro valerá 4 e o quarto valerá 8 devido ao bônus acumulado. Se todos os balões fossem estourados, o valor total seria 2+3+2+4=11.