Who dares to be a millionaire

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
Chef is going to participate in a new quiz show: "Who dares to be a millionaire?"
According to the rules of the game, contestants must answer N questions. The quiz being famous for its difficulty, each question has 26 candidate answers, but only one of which is correct. Answers are denoted by capital Latin letters from A to Z. Chef knows all the questions that can be asked, and for each of them he knows the answer candidate he will choose (some of them can be incorrect). For each question, we'll tell you Chef's answer to it.
The game goes on as follows. First, all the questions are shuffled randomly. Then, a contestant is asked these questions onebyone in the new shuffled order. If the contestant answers any question incorrectly, the game is over. Total winnings of the contestant are calculated as follows. Let X denote the number of questions answered correctly by the contestant. Depending on this value, the winnings are determined: W_{0} dollars is the amount won for X = 0, W_{1} dollars is for X = 1, and so on till X = N. Note that the game was invented by a twisted mind, and so a case where W_{i} ≥ W_{i + 1} for some 0 ≤ i ≤ N − 1 is possible.Chef is interested in finding the maximum possible winnings that he can amass.
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of questions.
Next line contains N capital Latin letters denoting the correct answers to these questions.
Next line contains N capital Latin letters denoting answers given by Chef to these questions.
Next line contains N + 1 spaceseparated integers W_{0}, W_{1}, ..., W_{N} denoting the winnings for 0, 1, ..., N correct answers.
Output
For each test case, output a single line containing the value of maximum possible winnings that Chef can get.
Constraints
 1 ≤ T ≤ 500
 1 ≤ N ≤ 1000
 0 ≤ W_{i} ≤ 10^{9}
Subtasks
Subtask 1: (20 points)
 1 ≤ N ≤ 8
Subtask 2: (80 points)
 Original constraints
Example
Input: 3 5 ABCDE EBCDA 0 10 20 30 40 50 4 CHEF QUIZ 4 3 2 1 0 8 ABBABAAB ABABABAB 100 100 100 100 100 100 100 100 100 Output: 30 4 100
Explanation
Example case 1. If questions will be placed in order: 2^{nd} (Chef's answer is B, which is correct), 3^{rd} (Chef's answer is C, and it is correct as well), 4^{th} (Chef's answer is D, and he is right), 5^{th} (Chef's answer is A but correct answer is E and the game is over), 1^{st}, Chef will correctly answer 3 questions, and therefore win 30 dollars.
Example case 2. Chef's answers for all questions are incorrect, so his winnings are W_{0} dollars.
Example case 3. Since all W_{i} are equal to 100 dollars, Chef will win this sum in any possible case.
Author:  eartemov 
Editorial  http://discuss.codechef.com/problems/WDTBAM 
Tags  adhoc, cakewalk, eartemov, oct15 
Date Added:  20072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions