Wordfeud

Wordfeud är ett scrabble/alfapet-liknande spel där man ska lägga ut bokstavsbrickor på en rutig spelplan så att det bildas ord. Orden kan läggas antingen från vänster till höger eller uppifrån och ned. Varje bokstav ger en viss poäng. Dessutom finns ett antal specialrutor på spelplanen, som kan vara av fyra typer:

• DL (double letter): bokstavspoängen för en bricka på denna ruta dubbleras

• TL (triple letter): bokstavspoängen för en bricka på denna ruta tredubblas

• DW (double word): poängen för hela ordet dubbleras om rutan täcks

• TW (triple word): poängen för hela ordet tredubblas om rutan täcks

När man räknar ut poängen för ett ord börjar man med att summera bokstavspoängen, med eventuell multiplikation på varje bokstav. När summan är uträknad multipliceras den med eventuella ordmultiplikatorer. Observera att om ordet ligger på flera DW- eller TW-rutor kan poängen multipliceras flera gånger.

I den här uppgiften tänker vi oss en tom $10$x$10$ spelplan där raderna och kolumnerna är numrerade enligt figuren. Skriv ett program som, givet specialrutornas placering på spelplanen och det ord du tänker lägga ut, beräknar den högsta poäng du kan få om du får lägga ordet var du vill (men hela ordet inom spelplanen).

Figure 1: Spelplanen i exemplet med specialrutorna utmärkta. De skuggade områdena visar tre exempel på placering av “ordet” $56141$. Den lodräta placeringen ger $2\cdot (2\cdot 5+6+1+2\cdot 4+1)=52$ poäng, den vågräta på rad $3$ ger $51$ poäng och den vågräta på rad $5$ ger $33$ poäng.

Input

På rad $1$ står antalet specialrutor, $N$, $1\leq N \leq 10$. Sedan följer $N$ stycken rader, en för varje specialruta. Varje rad består av två tal, raden respektive kolumnen för specialrutan (båda i intervallet $1$ till $10$), samt specialrutans typ (DL, TL, DW eller TW). Slutligen följer en sista rad, innehållandes ordet som ska läggas. För enkelhetens skull har varje bokstav redan ersatts med sitt poängvärde, en siffra mellan $0$ och $8$. Ordet kan ha upp till $7$ bokstäver.

Output

En rad, innehållandes den maximala poängen som är möjlig att få för det givna ordet.

5
2 7 DL
5 5 TL
6 7 DW
5 7 DL
3 6 TW
56141

52

4
1 9 DW
1 10 DL
2 9 TW
2 10 TL
174

72

9
1 1 DL
1 4 DW
3 1 TW
3 4 TL
2 3 TL
2 8 TW
9 3 DW
9 8 DW
9 2 DL
2152652

100