Every character in the string “IITMANDI” is given a certain number of points. You are given a scrabble board with only one row. The input contains the positions of score modifiers such as: Double Letter, Triple Letter, Double Word and Triple Word. You need to find the best position to place the string “IITMANDI” such that your score is maximized. 
Double Letter - Doubles the number of points you get for the letter placed on the double letter.
Triple Letter - Triples the number of points you get for the letter placed on the triple letter.
Double Word - Doubles the number of points you get for the word. Applied after applying above modifiers.
Triple Word - Triples the number of points you get for the word. Applied after applying the above modifiers.
The word has to be read from left to right. You can’t place it in the reverse direction.

The letters have to be placed continuously on the board.

If there is no modifier or a double word or triple word modifier before a tile, it's score is added to the total score. The double word and triple modifiers are applied at the end.

-----Input Format-----
- First line containes a single integer $T$ - the number of test cases.
- First line of each test case contains a single integer $N$ - the size of the board.    
- Second line of each test case contains a string of size $N$ representing the board according to the following convention:

'.' - No modifier

'd' - Double letter

't' - Triple letter

'D' - Double word

'T' - Triple word     
- Third line of each test case contains 8 integers corresponding to the points associated with each letter of the string "IITMANDI". Note that the 3 'I's in IITMANDI cannot be interchanged freely. The score of the first 'I' will be equal to the first integer, score of the second 'I' will be equal to the second integer and the score of the last 'I' will be equal to the last integer.

-----Output Format-----
For each test case, output a single integer in a new line, the maximum possible score. 

-----Constraints-----
$ 1 \leq T \leq 1000 $
$ 8 \leq N \leq 100 $
$ 0 \leq $ Points for each character $ \leq 10^5 $ 

-----Sample Input-----
2

10

..d.t.D..d

10 11 12 9 8 10 11 15

22

dtDtTD..ddT.TtTdDT..TD

12297 5077 28888 17998 12125 27400 31219 21536

-----Sample Output-----
270

35629632

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
try:
 
 T = int(input())

 for i in range(T):
  n = int(input())
  s = input()
  arr = [int(i) for i in input().strip().split(" ")]
  res = 1
  result = 0

  for j in range(n-7):
   res = 1
   res1= 0
   s1 = s[j:j+8]
   for i in range(8):
    if s1[i] == 'D':
     res = res*2
     res1 += arr[i]

    elif s1[i] == 'T':
     res = res*3
     res1 = res1 + arr[i]
    elif s1[i] == 'd':
     res1 = res1 + arr[i]*2
    elif s1[i] == 't':
     res1 += arr[i]*3
    else:
     res1 += arr[i]
   res = res*res1
   result = max(res,result)
  print(result)
except EOFError:
 pass

    
    
    
 
  
 


# cook your dish here
# cook your dish here
try:
 maxpoint=[]
 def maxpoints(n,string,sc):
  i=0
  points=0
  increaser=1
  while i<8:
   if string[i]=='.':
    points+=sc[i]
    i+=1
   elif string[i]=='d':
    points+=sc[i]*2
    i+=1
   elif string[i]=='t':
    points+=sc[i]*3
    i+=1
   elif string[i]=='D':
    increaser=increaser*2
    points+=sc[i]
    i+=1
   elif string[i]=='T':
    increaser=increaser*3
    points+=sc[i]
    i+=1
  points=points*increaser
  maxpoint.append(points)
  return points
 def values(n,string,sc):
  for i in range(n-7):
   maxpoints(n,string[i:],sc)
  return max(maxpoint)
 t=int(input())
 for i in range(t):
  n=int(input())
  string=str(input())
  if n>=8 and n==len(string):
   sc=list(map(int,input().split()))
   print(values(n,string,sc))
   maxpoint=[]
  else:
   print('String is not equals to the length given')
   break
except EOFError:
 pass

# cook your dish here
try:
 maxpoint=[]
 def maxpoints(n,string,sc):
  i=0
  points=0
  increaser=1
  while i<8:
   if string[i]=='.':
    points+=sc[i]
    i+=1
   elif string[i]=='d':
    points+=sc[i]*2
    i+=1
   elif string[i]=='t':
    points+=sc[i]*3
    i+=1
   elif string[i]=='D':
    increaser=increaser*2
    points+=sc[i]
    i+=1
   elif string[i]=='T':
    increaser=increaser*3
    points+=sc[i]
    i+=1
  points=points*increaser
  maxpoint.append(points)
  return points
 def values(n,string,sc):
  for i in range(n-7):
   maxpoints(n,string[i:],sc)
  return max(maxpoint)
 t=int(input())
 for i in range(t):
  n=int(input())
  string=str(input())
  if n>=8 and n==len(string):
   sc=list(map(int,input().split()))
   print(values(n,string,sc))
   maxpoint=[]
  else:
   print('String is not equals to the length given')
   break
except EOFError:
 pass

# cook your dish here
try:
 maxpoint=[]
 def maxpoints(n,string,sc):
  i=0
  points=0
  increaser=1
  while i<8:
   if string[i]=='.':
    points+=sc[i]
    i+=1
   elif string[i]=='d':
    points+=sc[i]*2
    i+=1
   elif string[i]=='t':
    points+=sc[i]*3
    i+=1
   elif string[i]=='D':
    increaser=increaser*2
    points+=sc[i]
    i+=1
   elif string[i]=='T':
    increaser=increaser*3
    points+=sc[i]
    i+=1
  points=points*increaser
  maxpoint.append(points)
  return points
 def values(n,string,sc):
  for i in range(n-7):
   maxpoints(n,string[i:],sc)
  return max(maxpoint)
 t=int(input())
 for i in range(t):
  n=int(input())
  string=str(input())
  if n>=8 and n==len(string):
   sc=list(map(int,input().split()))
   print(values(n,string,sc))
   maxpoint=[]
  else:
   print('String is not equals to the length given')
   break
except EOFError:
 pass

# cook your dish here
for e in range(int(input())):
 n = int(input())
 s = input()
 l = list(map(int,input().split()))
 s = list(s)
 m = 0
 for i in range(n-7):
  total = 0
  k = 0
  DT = 1
  for j in range(i,i+8):
   if s[j] == '.':
    total += l[k]
   elif s[j] == 'd':
    total += (2*l[k])
   elif s[j] == 't':
    total += (3*l[k])
   elif s[j] == 'D':
    DT = DT * 2
    total += l[k]
   elif s[j] == 'T':
    DT = DT * 3
    total += l[k]
   k += 1
   
  total = total * DT
  m = max(total, m)
   
   
 print(m)

try:
 maxpoint=[]
 def maxpoints(n,string,sc):
  i=0
  points=0
  increaser=1
  while i<8:
   if string[i]=='.':
    points+=sc[i]
    i+=1
   elif string[i]=='d':
    points+=sc[i]*2
    i+=1
   elif string[i]=='t':
    points+=sc[i]*3
    i+=1
   elif string[i]=='D':
    increaser=increaser*2
    points+=sc[i]
    i+=1
   elif string[i]=='T':
    increaser=increaser*3
    points+=sc[i]
    i+=1
  points=points*increaser
  maxpoint.append(points)
  return points
 def values(n,string,sc):
  for i in range(n-7):
   maxpoints(n,string[i:],sc)
  return max(maxpoint)
 t=int(input())
 for i in range(t):
  n=int(input())
  string=str(input())
  if n>=8 and n==len(string):
   sc=list(map(int,input().split()))
   print(values(n,string,sc))
   maxpoint=[]
  else:
   print('String is not equals to the length given')
   break
except EOFError:
 pass

try:
 maxpoint=[]
 def maxpoints(n,string,sc):
  i=0
  points=0
  increaser=1
  while i<8:
   if string[i]=='.':
    points+=sc[i]
    i+=1
   elif string[i]=='d':
    points+=sc[i]*2
    i+=1
   elif string[i]=='t':
    points+=sc[i]*3
    i+=1
   elif string[i]=='D':
    increaser=increaser*2
    points+=sc[i]
    i+=1
   elif string[i]=='T':
    increaser=increaser*3
    points+=sc[i]
    i+=1
  points=points*increaser
  maxpoint.append(points)
  return points
 def values(n,string,sc):
  for i in range(n-7):
   maxpoints(n,string[i:],sc)
  return max(maxpoint)
 t=int(input())
 for i in range(t):
  n=int(input())
  string=str(input())
  if n>=8 and n==len(string):
   sc=list(map(int,input().split()))
   print(values(n,string,sc))
   maxpoint=[]
  else:
   print('String is not equals to the length given')
   break
except EOFError:
 pass

# cook your dish here
maxpoints=[]
def maxvaluez(num,arr,sc):
 
 i=0
 points=0
 mult=1
 while i<8: 
  if arr[i]==".":
   points+=sc[i]
   i+=1

  elif arr[i]=="d":
   points+=2*sc[i]
   i+=1

  elif arr[i]=="t":
   points+=3*sc[i]
   

   i+=1

  elif arr[i]=="D":
   mult=mult*2
   points+=sc[i]
   i+=1

  elif arr[i]=="T":
   mult=mult*3
   points+=sc[i]
   i+=1

  else:
   i+=1
   

 points=points*mult
 maxpoints.append(points)
 return points
 
def maxpicker(num,arr,sc):
 for i in range(num-7):
  maxvaluez(num,arr[i:],sc)
 
 return max(maxpoints)

try:
 t=int(input())
 for i in range(t):
  num = int(input())
  arr = input()
  sc = list(map(int, input().split()))
  print(maxpicker(num,arr,sc))
  maxpoints=[]
except:
 pass

# cook your dish here
# cook your code here
t = int(input())
for i in range(t):
 num = int(input())
 arr = input()
 sc = list(map(int, input().split()))
 maxs = 0
 for z in range(num - 7):
  score = 0
  mul =1
  for b in range(8):
   if (arr[z+b]=='d'):
    score += sc[b]*2
   elif (arr[z+b]=='t'):
    score += sc[b]*3 
   elif (arr[z+b]=='D'):
    mul *= 2
    score += sc[b]
   elif (arr[z+b]=='T'):
    mul *= 3
    score += sc[b]
   else:
    score += sc[b]
  score *= mul
  if score > maxs:
   maxs = score
 print(maxs)


# cook your dish here
T = int(input())

max_score = []

for _ in range(T):

 N = int(input())
 string = input()
 score = input().split()
 score = list(map(int, score))

 
 noi = (N - 8 + 1)

 maximum = 0 
 
 for i in range(noi):

  dd = 0
  ttt = 0
  scrs = string[i:i+8]

  num_scrs = []
  for scr in scrs:

   if scr == '.':
    num_scrs.append(1)

   elif scr == 'd':
    num_scrs.append(2)

   elif scr == 't':
    num_scrs.append(3)

   elif scr == 'D':
    num_scrs.append(1)
    dd += 1

   elif scr == 'T':
    num_scrs.append(1)
    ttt += 1

  s = 0
  
  for i in range(8):
   s += num_scrs[i]*score[i]

  s *= 2**dd
  s *= 3**ttt

  if s > maximum:
   maximum = s
  
 max_score.append(maximum)


for s in max_score:

 print(s)


# cook your dish here
t=int(input())
for i in range(0, t):
 n=int(input())
 s=str(input())
 l=list(map(int, input().split()))
 sum1=sum(l)
 finalSum=0
 for i in range(n-7):
  sum2 = 0
  dw=1
  tw=1
  for k in range(i,i+8):
   if s[k]=="d":
    sum2=sum2+2*l[k-i]
   elif s[k]=="t":
    sum2 = sum2 + 3*l[k-i]
   elif s[k]=="D":
    dw*=2
    sum2 = sum2 + l[k - i]
   elif s[k]=="T":
    tw*=3
    sum2 = sum2 + l[k - i]
   else:
    sum2 = sum2 + l[k - i]

  # print(sum2)
  finalSum=max(finalSum,sum2*dw*tw)

 print(finalSum)

#cook
pos_values = {"d" : 2, "t" : 3, "." : 1, "D" : 1, "T" : 1}
T = int(input())
for i in range(T):
 N = int(input())
 positions = input()
 values = input()
 
 list_of_values = []
 temp = 0
 prev = 0
 i = 0
 while i < len(values):
  if values[i] == " ":
   temp = int(values[prev : i])
   list_of_values.append(temp)
   prev = i+1
   i += 1
  else:
   i += 1
 
 temp = int(values[prev : i])
 list_of_values.append(temp)
 
 set_of_values = []
 
 for j in range(N-7):
  temp = 0
  for k in range(8):
   temp += list_of_values[k]*pos_values.get(positions[j+k])
  
  for k in range(8):
   if positions[j+k] == "D":
    temp *= 2
   elif positions[j+k] == "T":
    temp *= 3
  
  set_of_values.append(temp)
 
 max_num = 0
 for l in range(len(set_of_values)):
  max_num = max(max_num, set_of_values[l])
 
 print(max_num)

#cook
pos_values = {"d" : 2, "t" : 3, "." : 1, "D" : 1, "T" : 1}
T = int(input())
for i in range(T):
 N = int(input())
 positions = input()
 values = input()
 
 list_of_values = []
 temp = 0
 prev = 0
 i = 0
 while i < len(values):
  if values[i] == " ":
   temp = int(values[prev : i])
   list_of_values.append(temp)
   prev = i+1
   i += 1
  else:
   i += 1
 
 temp = int(values[prev : i])
 list_of_values.append(temp)
 
 set_of_values = []
 
 for j in range(N-7):
  temp = 0
  for k in range(8):
   temp += list_of_values[k]*pos_values.get(positions[j+k])
  
  for k in range(8):
   if positions[j+k] == "D":
    temp *= 2
   elif positions[j+k] == "T":
    temp *= 3
  
  set_of_values.append(temp)
 
 max_num = 0
 for l in range(len(set_of_values)):
  max_num = max(max_num, set_of_values[l])
 
 print(max_num)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 s=list(input())
 N=[int(i) for i in input().split()]
 dic={'.':1,'d':2,'t':3,'D':1,'T':1}
 maxx=0
 for i in range(n-8+1):
  st=s[i:i+8]
  total=0
  D=0
  T=0
  for j in range(8):
   if st[j] in ['.','d','t']:
    total=total+dic[st[j]]*N[j]
   elif st[j]=='D':
    total=total+dic[st[j]]*N[j]
    D=D+1
   else:
    total=total+dic[st[j]]*N[j]
    T=T+1
  total=total*(2**D) 
  total=total*(3**T)
  if maxx<total:
   maxx=total
 print(maxx)

T = int(input())

max_score = []

for _ in range(T):

 N = int(input())
 string = input()
 score = input().split()
 score = list(map(int, score))

 
 noi = (N - 8 + 1)

 maximum = 0 
 
 for i in range(noi):

  dd = 0
  ttt = 0
  scrs = string[i:i+8]

  num_scrs = []
  for scr in scrs:

   if scr == '.':
    num_scrs.append(1)

   elif scr == 'd':
    num_scrs.append(2)

   elif scr == 't':
    num_scrs.append(3)

   elif scr == 'D':
    num_scrs.append(1)
    dd += 1

   elif scr == 'T':
    num_scrs.append(1)
    ttt += 1

  s = 0
  
  for i in range(8):
   s += num_scrs[i]*score[i]

  s *= 2**dd
  s *= 3**ttt

  if s > maximum:
   maximum = s
  
 max_score.append(maximum)


for s in max_score:

 print(s)

    
    
 



t = int(input())
maxi =[]
for _ in range(t):
 n = int(input())
 board = input()
 arr = input()
 points = list(map(int , arr.split(' ')))
 values = []
 for i in range(n-7):
  dw = 1
  tw = 1
  total = 0 
  for j in range(i,i+8):
   if board[j] == 'd':
    total += 2*points[j-i]
   elif board[j] == 't':
    total += 3*points[j-i]
   elif board[j] == 'D':
    dw *= 2
    total += points[j-i]
   elif board[j] == 'T':
    tw *= 3
    total += points[j-i]
   elif board[j] == "." :
    total += points[j-i]
   #print(total)
  
  total *= dw
  
  total *= tw 
  values.append(total)
 #print(values)
 maxi.append(max(values))
for element in maxi:
 print(element)



# cook your dish here
T=int(input())
while T:
 N=int(input())
 s=str(input())
 l=list(map(int,input().split()))
 
 re=[]
 for i in range(N-7):
  sum=0
  d1=1
  t1=1
  for j in range(len(l)):
   if s[i+j]==".":
    sum=sum+l[j]
   elif s[i+j]=="d":
    sum=sum+l[j]*2
   elif s[i+j]=="t":
    sum=sum+l[j]*3
   elif s[i+j]=="D":
    sum=sum+l[j]
    d1=d1*2
   elif s[i+j]=="T":
    sum=sum+l[j]
    t1=t1*3
 
  if d1>1 and t1>1:
   sum=sum*d1*t1
  elif d1>1:
   sum=sum*d1
  else:
   sum=sum*t1
  re.append(sum)
  
 print(max(re))
 T=T-1


# cook your dish here
t = int(input())
for z in range (t):
 n = int (input())
 board = input()
 b = list(board)
 #print(b)
 maxscore = 0
 scores = list(map(int , input().split()))
 #print(scores)
 for i in range(0 , n-7):
  #print(i)
  multiplier = 1 
  score = 0 
  for j in range (i,i+8):
   if (board[j]=="."):
    score += scores[j-i]
   elif(board[j]=="d"):
    score += scores[j-i]*2
   elif(board[j]=="t"):
    score += scores[j-i]*3
   elif(board[j]=="T"):
    score += scores[j-i]
    multiplier *= 3
   else:
    score += scores[j-i]
    multiplier *= 2
  maxscore= max ( maxscore , multiplier*score)
 print(maxscore)

for _ in range(int(input())):
 sum = 0; count = 0;max = 0;
 n = int(input())
 st = input()
 li = [int(i) for i in input().split(' ')]
 flag = True
 for i in range(n - 7):
  k = 0;count = 1;sum = 0;
  for j in range(i,i + 8):
   if st[j] == 'd':
    sum += li[k] * 2
   elif st[j] == 't':
    sum += li[k] * 3;
   elif st[j] == 'D':
    sum += li[k]
    count *= 2;
   elif st[j] == 'T':
    sum += li[k]
    count *= 3;
   else:
    sum += li[k]
   k += 1
  if flag == True:
   max = sum * count
   flag = False
  else:
   if sum * count > max:
    max = sum * count
 print(max)

for _ in range(int(input())):
 sum = 0; count = 0;max = 0;
 n = int(input())
 st = input()
 li = [int(i) for i in input().split(' ')]
 flag = True
 for i in range(n - 7):
  k = 0;count = 1;sum = 0;
  for j in range(i,i + 8):
   if st[j] == 'd':
    sum += li[k] * 2
   elif st[j] == 't':
    sum += li[k] * 3;
   elif st[j] == 'D':
    sum += li[k]
    count *= 2;
   elif st[j] == 'T':
    sum += li[k]
    count *= 3;
   else:
    sum += li[k]
   k += 1
  if flag == True:
   max = sum * count
   flag = False
  else:
   if sum * count > max:
    max = sum * count
 print(max)

T = int(input())
for j in range(T):
 n = int(input())
 ar = input()
 ar_v = list(map(int, input().split()))
 mx=0
 for i in range(n-7):
  sm =0
  m=1
  
  for k in range(8):
   if ar[i+k]=='.':
    sm +=ar_v[k]
   elif ar[i+k]=='d':
    sm =sm+ (2*ar_v[k])
   elif ar[i+k]=='t':
    sm =sm+(3*ar_v[k])
   elif ar[i+k]=='D':
    sm =sm+ar_v[k]
    m *=2
   elif ar[i+k]=='T':
    sm =sm+ar_v[k]
    m *=3
  sm = sm*m
  #print(sm)
  if mx<sm:
   mx=sm
 print(mx)

# cook your dish here
T = int(input())
for j in range(T):
 n = int(input())
 ar = input()
 ar_v = list(map(int, input().split()))
 mx=0
 for i in range(n-7):
  sm =0
  m=1
  
  for k in range(8):
   if ar[i+k]=='.':
    sm +=ar_v[k]
   elif ar[i+k]=='d':
    sm =sm+ (2*ar_v[k])
   elif ar[i+k]=='t':
    sm =sm+(3*ar_v[k])
   elif ar[i+k]=='D':
    sm =sm+ar_v[k]
    m *=2
   elif ar[i+k]=='T':
    sm =sm+ar_v[k]
    m *=3
  sm = sm*m
  #print(sm)
  if mx<sm:
   mx=sm
 print(mx)

t=int(input())
while(t>0):
 n=int(input())
 s=str(input())
 A=list(map(int,input().split()))
 maxi=0
 for i in range(0,n-7):
  summ=0
  new=""
  k=0
  for j in range(i,i+8):
   if(s[j]=='D' or s[j]=='T'):
    new=new+s[j]
   if(s[j]=='d'):
    summ+=(2*A[k])
   elif(s[j]=='t'):
    summ+=(3*A[k])
   else:
    summ+=A[k]
   k+=1
  for x in new:
   if(x=='D'):
    summ=(2*summ)
   else:
    summ=(3*summ)
  if(summ>maxi):
   maxi=summ
 print(maxi)
 t=t-1

#!/bin/python3

import math
import os
import random
import re
import sys

def findMaxScore(mod, arr):

 m = 0

 for i in range(0,len(mod)-7):
  m = max(m,getScore(mod[i:i+8],arr))

 return m

def getScore(s,arr):
 
 m = 1

 score = 0

 for i in range(0,8):

  if(s[i] == 'd'):
   score += 2*arr[i]
  elif(s[i] == 't'):
   score += 3*arr[i]
  elif(s[i] == 'D'):
   score += arr[i]
   m *= 2
  elif(s[i] == 'T'):
   score += arr[i]
   m *= 3
  else:
   score += arr[i]
 
 return m*score

def __starting_point():
 
 try:
  n = int(input())
 
  for _ in range(n):
   
   l = int(input())
   mod = input()
   arr = [int(y) for y in input().split()]
   print(findMaxScore(mod,arr))
 
 except EOFError:
  x = 2
__starting_point()

# cook your dish here
# cook your dish here
def calc(W,board):
 #print(board)
 d = t = score = 0
 for i in range(8):
  if board[i]=='d': score+= (2*W[i])
  elif board[i]=='t': score+= (3*W[i])
  elif board[i] == 'D': 
   d += 1
   score += W[i]
  elif board[i] == 'T': 
   t+=1
   score += W[i]
  else: score += W[i]
  #print("i=",i,"score=",score)
 #print("d=",d,"t=",t)
 score *= 2**d * 3**t
 #if t>0: score = 3*t*score
 #print("\nvv",score,"\n")
 #print(len(str(score)))
 #print("--------------------------------------------")
 return score
 
def __starting_point():
 output = ""
 for test in range(int(input())):
  N = int(input())
  board = input()
  W = [int(x) for x in input().split()]
  m = -1
  for i in range(N-7):
   #print(board[i:i+8])
   m = max(m,calc(W,board[i:i+8]))
  output += str(m)+"\n"
 print(output.rstrip())
__starting_point()