Scrambled Scrabble
Hanyuan has recently been playing a lot of scrabble but is struggling to maximise the points he is getting on each word. Given a string with some spots filled with letters and the others hyphens, and a list of letters that Hanyuan has access to, can you find the maximum score he can achieve?
Fortunately, the words we create do not have to be real English words. The bank of letters we are given will also be the same length as the length of word we are trying to create. Note that spots in the target word with hyphens are where we need to put our letters.
Rules
- Each letter will have a value corresponding to its position in the alphabet (, etc.)
- Each consonant must be followed by a vowel and each vowel must be followed by a consonant. (“abed” is valid, “abcd” is not). Words can start with either a consonant or vowel.
- No letter from the letter bank can be used more than once. Note there may be duplicate letters in the letter bank, you can use both.
Input Format
You will receive 3 lines as input.
The first is an integer .
Next will be the target word of length , with some letters filled in and hyphens where you insert other letters. You may assume that the target word will always contain at least one letter, i.e you will never be given a target word consisting of all hyphens.
Finally will be the letter bank of length in reverse alphabetical order.
Constraints
Output Format
If a word can be formed, print to stdout the value of the word. If a word cannot be formed, print "Cannot be done!".
Sample Input 0
6
a-eci-
zyhdcb
Sample Output 0
69
Explanation 0
The highest scoring words we can make are “azeciy” or “ayeciz”. Assume we use "azeciy" as our word, then we calculate the score as .
Sample Input 1
5
--ap-
ufdcb
Sample Output 1
Cannot be done!
Explanation 1
There are 3 spots we need to fill using two vowels and a consonant. There is only one vowel in the letter bank we were given, hence we cannot form a word.