Virkņu pagarināšana

Uzdevums

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

Teksta fails pagarin.dat 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.

Izvaddati

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

Piemērs

pagarin.dat	pagarin.rez
cmc snmn 2	10
pagarin.dat	pagarin.rez
koiv ua 1	5
pagarin.dat	pagarin.rez
mj jao 4	12

Atsauces