Moein's Chocolates

Time Limit: 5 Seconds    Memory Limit: 131072 KB

محسن و معین در اوقات فراغتشان در خانه با هم بازی زیر را انجام می‌دهند. محسن دو کلمه تشکیل شده از حروف کوچک لاتین انتحاب می‌کند و آنها را به معین می‌دهد.معین باید با تعدادی عملیات این دو رشته را به دورشته یکسان تبدیل کند. او در هر عملیات می‌تواند یکی از حروف یکی از دو رشته را تبدیل به یک حرف دیگر کند. محسن برای این که بازی را برای معین سخت تر کند حرکات معین را محدود می‌کند (معین دیگر نمی‌تواند به جای هر حرف هر حرف دیگری را بگذارد) و برای هر حرکتش تعدادی شکلات از او می‌گیرد. معین ناراحت می‌شود ولی از آنجایی که توان مقابله با حرف محسن را ندارد مجبور است با او موافقت کند. ولی از آنجایی‌که نمی‌خواهد شکلات‌هایش از دست برود می‌خواهد این دو رشته را به نحوی به هم تبدیل کند (یا هر دو را به یک رشته میانی تبدیل کند) که کمترین شکلات را به محسن بدهد. او از شما که درس ساختمان داده را می‌خوانید و در حل این گونه سوالات قوی هستید می‌خواهد که به او کمک کنید.

Input

در دو خط ابتدای ورودی دو رشته ای که معین باید به هم تبدیل کند آمده است. در خط بعد تعداد حرکات مجاز k آمده است. در k خط بعدی در هر خط دو کاراکتر و یک عدد طبیعی آمده است به معنای آن که معین می‌تواند کاراکتر اول را به کاراکتر دوم با این هزینه(شکلات) تبدیل کند.

 طول رشته‌ها حداکثر ۱۰^۵ است و تعداد حرکات مجاز نیز حداکثر ۵۰۰ تاست.به ازای هر حرکت محسن حداکثر۱۰۰ شکلات از معین می‌گیرد.

Output

اگر معین نمی‌تواند دو رشته را به هم تبدیل کند ۱- چاپ کنید و در غیر این صورت تعداد شکلات‌هایی که معین در بهترین حالت تبدیل کردن دو رشته باید به محسن بدهد را چاپ کنید.

Sample Input

mohsen
dadash
9
m d 10
m a 4
a d 2
o a 2
a o 3
d h 3
o s 1
s e 1
h n 1
moein
kolah
5
h n 5
a i 1
k m 5
d e 1
s a 17
m
a
2
s a 1
s m 1
m
a
2
m s 10
a s 7

Sample Output

17
-1
-1
17

Submit