The alphabetical sum of an alphabetic string is defined as the sum of the indices of each character in the alphabet. For example, the alphabetical value of the string
abce is , since the indices of
e are , , , and , respectively, and .
Steven has a string which consists strictly of lowercase letters and asterisks. The asterisks can each be replaced with any lowercase letter in the English alphabet.
Given an integer , representing Tommy's desired alphabetical sum, Steven wonders whether it is possible to construct a string with an alphabetical sum of by replacing the asterisks in his string. If it is, he wants to know the lexicographically smallest such string.
Definition: A string is lexicographically smaller than a string if and at the first index where , .
The input consists of two lines. The first line contains , representing Tommy's desired alphabetical sum. The second line contains , representing the string Steven has.
The following table shows how the available 15 marks are distributed.
|Mark Awarded||Expected Alphabetical Value||Length of Steven's String|
If it is impossible to construct a string that satisfies Tommy's expectations, output
Otherwise, output the lexicographically smallest string such that the alphabetical sum of the string is .
Sample Input 1
Output for Sample Input 1
Explanation of Output for Sample Input 1
The alphabetical sum of
aa is . It can be shown that
aa is the only possible string in this case.
Sample Input 2
Output for Sample Input 2
Explanation of Output for Sample Input 2
The alphabetical value of
aab is . Other possible strings like
aba also have as the alphabetical sum, but
aab is the lexicographically smallest.
Sample Input 3
Output for Sample Input 3
Explanation of Output for Sample Input 3
It can be shown that we cannot construct a string for this case that has an alphabetical sum of .