Sopa de lletres amb punts P87801

Statement

Considereu un tauler $f \times c$ on cada casella té una lletra i un nombre que diu quant val aquella casella. Donades diverses paraules $p$ , cal dir el màxim nombre de punts que es pot aconseguir posant $p$ horitzontalment (cap a la dreta) o verticalment (cap avall), de manera que totes les lletres coincideixin amb les del tauler.

Entrada

L’entrada consisteix en diversos casos, cadascun amb les dimensions $f$ i $c$ , seguides de $f$ files amb $c$ lletres minúscules cadascuna, seguides de $f$ files amb $c$ naturals cadascuna. Després ve un nombre $t$ seguit de $t$ paraules no buides formades amb lletres minúscules. Podeu suposar que $f$ i $c$ estan entre 1 i 100, que el valor de cada casella es troba entre 0 i $10^6$ , i que les paraules donades no tenen més de 100 lletres.

Sortida

Per a cada paraula de cada cas, escriviu la màxima puntuació possible posant la paraula horitzontalment o verticalment. Si la paraula no hi és, escriviu “no”.

Public test cases

Input

3 4
a b c a
b c a e
c a b d
10 20 30 40
50 60 70 80
15 25 35 45
3
bca
cabb
a

1 1
z
1000000
2
y
z

Output

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++ Python
User solutions: C++ Python