設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多個(gè)空格后構(gòu)成的新字符串為X的擴(kuò)展串，如字符串X為“abcbcd”，則字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的擴(kuò)展串，這里“□”代表空格字符。 如果A1是字符串A的擴(kuò)展串，B1是字符串B的擴(kuò)展串，A1與B1具有相同的長(zhǎng)度，那么我們定義字符串A1與B1的距離為相應(yīng)位置上的字符的距離總和，而兩個(gè)非空格字符的距離定義為它們的ASCII碼的差的絕對(duì)值，而空格字符與其它任意字符之間的距離為已知的定值K，空格字符與空格字符的距離為O。在字符串A、B的所有擴(kuò)展串中，必定存在兩個(gè)等長(zhǎng)的擴(kuò)展串A1、B1，使得A1與B1之間的距離達(dá)到最小，我們將這一距離定義為字符串A、B的距離。 請(qǐng)你寫一個(gè)程序，求出字符串A、B的距離。

輸入文件第一行為字符串A，第二行為字符串B，A、B均由小寫字母組成且長(zhǎng)度均不超過2000，第三行為一個(gè)整數(shù)K，1≤K≤100，表示空格與其它字符的距離。

輸出文件僅一行包含一個(gè)整數(shù)，表示要求的字符串A、B的距離。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

名校訓(xùn)練 動(dòng)態(tài)規(guī)劃