<PREV Problem:
NEXT>
Solved by 192 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

War-cry

Time limit = 4

Chieftains of Mumba-Lumba decided make up new war-cry to increase martial spirit and to frighten enemy.

Alphabet B of Mumba-Lumba consists of M letters. War-cry should be word in this alphabet of length N. Scientists of Mumba-Lumba found out set of different elementary screams (words in the alphabet B) {s1 s2 ... sk} which arouse fear in enemy equal to {f1 f2 ... fk} correspondingly. Number fi is nonnegative integer less than 10000.

Each instance of word si in war-cry adds to its fearness number fi.

Number fi may not be equal to fierness of the word si, because si may contains one or more other elementary screams as subwords.

Input First line contains three numbers N, M and K delimited with space. K is the number of elementary screams. 1 ≤ N ≤ 100, 1 ≤ M ≤ 25, 1 < K ≤ 100. Next line contains Mubma-Lubma alphabet — different lowcase latin letters. Next lines contain information about elementary screams. Each line has format of

< word > < it's fearness >

Output Maximum value of fearness among words of length N and example of word of length N with this fearness in the next line.

Input#1
4 3 4
abc
a 1
b 1
ab 3
caa 6
Output#1
12
caab

Input#2
7 10 4
abcdefghij
a 1
b 1
ab 4
bac 8
Output#2
25
bacabac

Author:
From Moscow school programming contest (modified, complicated).
december 2002

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 23.20.13.165