Howl
The leaders of the renowned Mumba-Yumba tribe have decided to create a new battle cry for their warriors. This cry must be exactly N letters long, using letters from the tribe's alphabet, which consists of M letters. Through extensive research, they discovered that if the cry includes the word s_i (a sequence of up to three alphabet letters), it generates f_i units of fear in the enemy. If the cry contains multiple such words, their fear-inducing effects are cumulative. For instance, if the cry includes the words s_i and s_j, it will instill f_i+f_j units of fear.
Your task is to construct the most fearsome cry possible, given N, M, the alphabet, and the list of fearsome words s_i.
Input
The first line contains three numbers: N, M, and K (0 < N ≤ 100, 0 < M < 25, 0 ≤ K ≤ 100), where K is the number of fearsome words. The second line contains the alphabet, which is a string of M lowercase Latin letters. The next K lines each provide a word and its associated fearfulness value (0 < f_{i} ≤ 10000).
Output
The output should display the total fearfulness of the most fearsome cry that can be composed.