Ir divas simbolu virknes - A un B, kas katra sastāv no angļu alfabēta mazajiem burtiem.

Kādas simbolu virknes X pagarināšana notiek, iespraužot tajā patvaļīgu skaitu (0 vai vairāk)pasvītrojuma simbolu jebkurā tās vietā (sākumā, beigās vai pa vidu). Ja virkne X ir 'abcbcd', tad tai atbilstošās pagarinātās virknes ir, piemēram, 'abcb_cd', '_a_bcbcd_' un 'abcb_cd_'.

Ja A₁ ir virknes A pagarinātā virkne, bet B₁ ir virknes B pagarinātā virkne un virknes A₁ un B₁ ir vienāda garuma, tad var aprēķināt attālumu starp šīm virknēm kā attālumu starp šo virkņu atbilstošajiem simboliem summu. Attālums starp diviem burtiem ir šo burtu ASCII kodu starpības absolūtā vērtība. Attālums starp burtu un pasvītrojuma zīmi ir dots naturāls skaitlis (šis skaitlis ir viens un tas pats visiem burtiem).

Uzrakstiet programmu, kas dotām virknēm A un B atrod mazāko iespējamo attālumu starp šo virkņu pagarinātajām virknēm A₁ un B_1!

Ievaddati sastāv no trim rindām - pirmajā rindā dota virknes A, otrajā - virknes B vērtība, bet trešajā naturāla skaitļa K (attālums no pasvītrojuma zīmes līdz burtam, 1≤K≤100) vērtība. Virkņu A un B garums nepārsniedz 2000 burtus.

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais iespējamais attālums starp A₁ un B_1.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā