B. Ижил тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валера нэртэй хүү тэмдэгт мөрөнд дуртай төдийгүй тэмдэгт мөрнүүд хоорондоо ижил бол илүү дуртай юм. Тиймээс тэрээр чөлөөт цагаараа дараах тоглоомыг тоглодог. Хүү дурын $2$ Латин жижиг үсэгнээс бүтсэн тэмдэгт мөрийг аван түүнийг адил болгох гэж оролддог. Тоглоомын дүрэм нь Валера нүүдэл болгондоо дурын байрлалд байрлах $A_{i}$ үсэгийг $B_{i}$ үсэг болгон өөрчилж чадна. Гэвч нүүдэл болгонд $W_{i}$-тэй дүйх хэмжээний төлбөр төлөх ёстой. Хүү хэрэгтэй бол хэдэн ч нүүдэл хийж болно. Валера ариг гамтай хүүхэд болохоор өөрийн мөнгийг дэмий үрдэггүй. Тиймээс хүү таниас тэмдэгт мөрнүүдийг ижил болгохын тулд хамгийн багадаа хэр их мөнгө зарцуулахыг тооцож өгөхийг хүсчээ.

Оролт

Эхний хоёр мөрөнд мөр бүрд хоосон биш $s$ ба $t$ тэмдэгт мөрүүд өгөгдөнө. Тэмдэгт мөр нь Латин жижиг үсэгнээс бүтэх бөгөөд тэмдэгт мөр болгоны урт $10^{5}$-ээс хэтрэхгүй.

Дараагийн мөрөнд $n$ ($0 ≤ n ≤ 500$) бүхэл тоо буюу нийт өөрчлөх боломжтой үсэгнүүдийн тоо өгөгдөнө. Дараагийн $n$ мөрөнд мөр болгонд $A_{i}$, $B_{i}$ (Латин жижиг үсэгнүүд) үсэгнүүд болон $W_{i}$ ($0 ≤ W_{i} ≤ 100$) бүхэл тоо өгөгдөнө. $A_{i}$ үсэгийг $B_{i}$-ээр солиход $W_{i}$ хэмжээний мөнгө төлнө.

Гаралт

Хэрвээ тэмдэгт мөрүүдийг тэнцүү болгох боломжтой байвал эхний мөрөнд хариуг хэвлэн, дараагийн мөрөнд ижил болох тэмдэгт мөрийг хэвлэнэ. Харин энэ нь боломжгүй байвал "-1" гэж ганц мөрөнд хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
uayd
uxxd
3
a x 8
x y 13
d c 3
Гаралт
21
uxyd
Оролт
a
b
3
a b 2
a b 3
b a 5
Гаралт
2
b
Оролт
abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...