Word Coins
Турнир за Купата на Декана, 2016
Time Limit: 0.1s, Memory Limit: 64MiB
След като мина през BitCoins, LiteCoins, DogeCoins, и какви ли още не криптовалути, сега Ели търгува с WordCoins.

За разлика от другите валути, тук всяка "банкнота" е една дума, състояща се от главни латински букви. Понякога банкнота може да бъде заменена с друга, като в зависимост от двете думи при трансакцията или единият участник плаща на втория допълнително левове, или получава такива. Разменянето се случва по следния начин: ако собственик на дума L иска да я замени за дума R, то за всеки символ i той плаща (или получава, в случай, че разликата е отрицателна) R[i] – L[i] лева, където буквата 'A' е със стойност 1, 'B' е със стойност 2, и така нататък, до буквата 'Z', която е със стойност 26.

Така, например, ако Ели има думата "BIRA" и иска да си купи "CACA", то тя би платила ('C'-'B') + ('А'-'I') + ('C'-'R') + ('A'-'A') = (3-2) + (1-9) + (3-18) + (1-1) = 1 - 8 -15 + 0 = -22 лева, тоест трябва да даде "BIRA" на другия човек, а в замяна ще получи "CACA" и 22 лева. Ако пък имаше "GARGA" и купуваше "TORTA" щеше да трябва да даде 40 лева за да извърши трансакцията.

В случай, че думите са с различна дължина, по-късата дума се допълва с фиктивни символи със стойност 0. Например ако имаме "KUPA", и искаме да я заменим за "DEKANA", то изчисляваме разликата на "DEKANA" - "KUPA__" = -13 (забележете, че тук заменяме по-къса дума за по-дълга и все пак печелим пари).

Ели знае, че на пазара се търгуват M думи: стига да има Li, момичето може да я размени за Ri (заплащайки или получавайки съответната разлика в лева). Ели в началото има думата S и иска да придобие G. Сега се чуди каква е минималната цена (или максималната печалба, в случай, че цената е отрицателна), която трябва да плати. Гарантирано е, че с позволените размени от S може да се получи G.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число M – броя думи, които могат да бъдат разменяни. Следват M реда, всеки съдържащ по два стринга Li и Ri, съставени от главни латински букви. На последния ред за теста ще бъдат зададени още два стринга S и G – съответно стринга, който в началото има Ели, и този, който иска да получи.
Изход
На стандартния изход изведете едно цяло число – минималната цена, която трябва да заплати Ели. В случай, че тя ще завърши с повече пари, отколкото е започнала, числото трябва да е отрицателно.
Ограничения
  • 1 ≤ M ≤ 1,000
  • Дължината на всички стрингове във входа е между 1 и 30 символа.
Примерен Вход Примерен Изход
10 BABA CECA LEPA BRENA BIRA CACA CACA CECA MUHATA HAHAHA HAHAHA BIRA MUHATA DIVAN DIVAN BABA CECA SLON CECA LEPA MUHATA SLON -4
18 PARI KRUSHI PARI QBYLKI PARI SLIVI PARI CHERESHI PARI QGODI PARI BOROVINKI PARI GROZDE KRUSHI RAKIQ RAKIQ NOMNOMNOM QBYLKI SOK SOK NOMNOMNOM SLIVI RAKIQ SLADKO NOMNOMNOM CHERESHI SLADKO QGODI SLADKO BOROVINKI SLADKO GROZDE VINO VINO NOMNOMNOM PARI NOMNOMNOM 82
В първия пример искаме от "MUHATA" да направим "SLON". Едно от оптимално решение е да ползваме заменянията: "MUHATA" -> "HAHAHA" -> "BIRA" -> "CACA" -> "CECA" -> "SLON". В него правим пет размени, струващи, съответно, (-37) + 3 + (-22) + 4 + 48 = -4. Във втория пример с "PARI" можем да си купим "BOROVINKI", които пък да направим на "SLADKO" и накрая да получим "NOMNOMNOM".
Мрън!