In this problem, every string has a beauty value which is represented as a positive integer.
The elegance of a sequence of strings is defined as
Diane has strings , each consisting of the digits to , and has beauty value . She would like to form the most elegant sequence of strings among them. She can write any string with her digit cards; for every digit from to , she has exactly cards in which the digit is written, so she has cards in total. For example, 1 digit card each for every number to would be,
Furthermore:
- She may write the strings in any order, but she can only form each string at most once.
- To write a string, she has to use the cards. But each card can only be used once, so it may not be possible to write all strings.
Given the above restrictions, what is the maximum elegance of any sequence that Diane can form?
Complete the function maximumElegance which takes in an integer , an array consisting of strings, and an array consisting of integers denoting their respective beauty values and returns the maximum elegance of any sequence that Diane can form.
Input Format
The first line contains two space-separated integers and .
The second line contains space-separated integers denoting the beauty values of the strings.
The of the next lines contains the string, .
Constraints
- is a string of digits -.
Subtask
- For ~20% of the total score,
Output Format
Print a single integer denoting the maximum elegance which can be obtained by Diane.
Sample Input 0
3 2
2 3 1
1032
2467
48957
Sample Output 0
8
Explanation 0
Note that , which means we have two cards for each digit, and so we can write all three strings.
If we write all three strings in the order , then we get an elegance of , which is the maximum possible.