Wordfeud

Wordfeud는 글자 타일을 격자형 게임판에 놓아 단어를 만드는 Scrabble/Alfapet과 비슷한 게임이다. 단어는 왼쪽에서 오른쪽으로 또는 위에서 아래로 놓을 수 있다. 각 글자는 일정한 점수를 준다. 또한 게임판에는 다음 네 가지 유형의 특수 칸이 여러 개 있다:

• DL (글자 점수 두 배): 이 칸에 놓인 타일의 글자 점수가 두 배가 된다

• TL (글자 점수 세 배): 이 칸에 놓인 타일의 글자 점수가 세 배가 된다

• DW (단어 점수 두 배): 이 칸을 덮으면 단어 전체의 점수가 두 배가 된다

• TW (단어 점수 세 배): 이 칸을 덮으면 단어 전체의 점수가 세 배가 된다

단어의 점수를 계산할 때는 먼저 각 글자에 적용되는 배수를 반영하여 글자 점수를 합산한다. 합을 계산한 뒤에는 적용되는 단어 배수를 곱한다. 단어가 여러 개의 DW 또는 TW 칸에 걸쳐 있으면 점수가 여러 번 곱해질 수 있음에 유의하라.

이 문제에서는 그림과 같이 행과 열에 번호가 매겨진 빈 $10$x$10$ 게임판을 사용한다. 게임판에서 특수 칸의 위치와 놓으려는 단어가 주어질 때, 단어 전체가 게임판 안에 있도록 원하는 곳에 단어를 놓아서 얻을 수 있는 최대 점수를 계산하는 프로그램을 작성하라.

[!h]

예제의 게임판에서 특수 칸이 표시되어 있다. 음영 영역은 “단어” $56141$을 놓는 세 가지 예를 보여 준다. 세로로 놓으면 $2\cdot(2\cdot5+6+1+2\cdot4+1)=52$점, $3$행에 가로로 놓으면 $51$점, $5$행에 가로로 놓으면 $33$점을 얻는다.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 받으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$50$| DW와 TL는 입력에 등장하지 않는다.

$2$ |$50$| 추가 제한이 없다.

첫째 줄에 특수 칸의 수 $N$ ($1\leq N \leq 10$)이 주어진다.

이어지는 $N$개의 줄에는 각각 하나의 특수 칸이 설명된다. 각 칸은 특수 칸의 행과 열을 나타내는 두 수(둘 다 $1$부터 $10$까지의 범위)와 특수 칸의 유형(DL, TL, DW 또는 TW)으로 구성된다.

마지막으로 놓을 단어가 담긴 한 줄이 주어진다. 편의를 위해 각 글자는 이미 그 점숫값인 $0$부터 $8$까지의 숫자로 대체되어 있다. 단어는 최대 $7$개의 글자로 이루어진다.

주어진 단어로 얻을 수 있는 최대 점수를 나타내는 정수 하나를 출력한다.