Scowbble! It's another rainy day at the farm so the cows have to stay inside the barn. In order to avoid boredom they decide to play a game. This game is played on a 15x15 board. Every cow gets N letters (1 <= N <= 7) for her 'hand' and tries to make words by combining the letters in her hand given and the ones currently on the board. A cow can make a word by placing letters in only one row or one column. Every letter must be adjacent to another one and at least one letter placed must be adjacent to one letter previously on the board. Whenever a cow finishes placing the letters she desires every word that is formed horizontally or vertically to be valid (i.e., a word that exists in Bessie's dictionary). Each letter A..Z has a value so when a cow's turn is finished the cow gets as many points as the sum of the values of letters of every word created. A cow gets additionally 20 points if she uses all the letters she has in her hand (or hoof). Given the state of the board and the letters available find the maximum points that a cow can get in her turn. Bessie's dictionary has no more than 25,000 words. PROBLEM NAME: scowbble INPUT FORMAT: * Line 1: A single integer: N * Line 2: N space-separated letters * Line 3: 26 integers representing the value of every letter A..Z * Lines 4..18: The 15 letters of every line of the board. There will always exist at least one word. (The empty cells are represented with '*') * Lines 19.....: Farmer John's dictionary follows with one word per line. The dictionary ends with a line containing the character 'e' (which is not a word). SAMPLE INPUT: 5 S B L E B 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 * * * * * N * * * * * * * * * * * * * C O W * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * COW COWS SCOWBBLE NO NOBEL e OUTPUT FORMAT: The maximum points you can get SAMPLE OUTPUT: 28 OUTPUT DETAILS: You get 8 points making the word SCOWBBLE + 20 for using all the letters.