The leaders of the famous Mumba Yumba tribe decided to come up with a new battle cry for their warriors. At the same time, they decided that the cry should consist of exactly N letters (there are M letters in the alphabet of the tribe). Also, after much research, it was found out that if the word s
i (the word – is a sequence of letters of the alphabet, no longer than three characters) is found in the scream, then this scream instills f
in the enemy i units of fear. If a cry includes several words, then their “terrible” summed up. For example, if a yell contains the words s
i and s
j, then the yell instills f
i+f
j units of fear .
Given N, M, the alphabet and the list of words s
i, it is required to compose the most terrible scream.
Input:
The first line contains three numbers – N, M and K (0<N≤100, 0<M<25, 0<K≤100), where K– number of scary words. The next line contains the alphabet – a string of M lowercase Latin letters. Next, K lines contain information about the words – the word itself and, separated by a space, one number denoting the scariness of this word (0 < f
i ≤ 10000).
Output:
In the output file, you need to output the scariness of the received scream and on the next line – the scream itself.
Examples
| # |
Input |
Output |
| 1 |
3 5 4
abc
abc 10
ab 5
be 7
e 4 |
16
abe |