<PREV Problem:
NEXT>
Solved by 194 users: ...
UserDateAttemptTimeCMSC
david_it2113 may 2008C++1300.0495 
Nakilon06 may 2010Ruby617.05155 
fetetriste17 dec 2009C++100.32439 
12whoami3410 aug 2012Ruby700.08500 
mathematic16 sep 2012C++100.15500 
mukel124 jul 2008C++800.04555 
mukel30 oct 2010C++100.05555 
a2zaruna22 aug 2006C++600.16602 
Zorgan25 mar 2010C++1500.02606 
abortmozga.ru28 may 2010C++601.18611 
Languages
C++
126
FPC
45
Kylix
12
Java
6
C
4
Ruby
2
Python
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 = 3.237.200.21