Nosaukums
Virkņu pagarināšana (pagarin)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

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 A1 ir virknes A pagarinātā virkne, bet B1 ir virknes B pagarinātā virkne un virknes A1 un B1 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 A1 un B1!


Ievaddatu raksturojums

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 raksturojums

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


Piezīmes

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


Paraugdati

Stdin
cmc
snmn
2
Stdout
10

Stdin
koiv
ua
1
Stdout
5

Stdin
mj
jao
4
Stdout
12

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.