시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB19111055.556%

문제

어떤 문자열 X의 확장이란 그 문자열의 어떤 위치 또는 가장 앞과 뒤에 공백을 임의의 개수(0, 1또는 그 이상)만큼 추가하는 것이다. 예를 들어, 문자열 X가 'abcbcd'일 때, 'abcb-cd', '-a-bcbcd-', 'abcd-cd-'는 문자열 X의 확장이 된다. (공백은 '-'로 표시)

A1을 문자열 A의 확장이라고 하고, B1을 문자열 B의 확장이라고 했을 때, A1과 B1의 길이가 같다면, 두 문자열의 거리를 정의할 수 있다. 두 문자열의 거리란, 같은 위치에서 문자의 거리의 합이다. 문자의 거리란, ASCII 코드 값의 차이를 말한다. 이때, 공백과 다른 문자와의 차이는 입력으로 주어지는 K이다.

두 문자열 A와 B가 주어졌을 때, 가장 짧은 거리를 갖는 A1과 B1을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 문자열 A가 주어진다. 둘째 줄에는 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 2000보다 작거나 같다. 셋째 줄에는 공백과 다른 문자와의 거리 K가 주어진다. (1 ≤ K ≤ 100)

출력

첫째 줄에 가장 짧은 거리를 출력한다.

예제 입력 1

cmc
snmn
2

예제 출력 1

10

예제 입력 2

koiv
ua
1

예제 출력 2

5

예제 입력 3

mj
jao
4

예제 출력 3

12
W3sicHJvYmxlbV9pZCI6IjMyNjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVkNjU1XHVjN2E1XHVhY2ZjIFx1YWM3MFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBYXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc4MCBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM3MDRcdWNlNTggXHViNjEwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NWVcdWFjZmMgXHViNGE0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWM3ODRcdWM3NThcdWM3NTggXHVhYzFjXHVjMjE4KDAsIDFcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMSlcdWI5Y2NcdWQwN2MgXHVjZDk0XHVhYzAwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjNzkwXHVjNWY0IFhcdWFjMDAgJiMzOTs8Y29kZT5hYmNiY2Q8XC9jb2RlPiYjMzk7XHVjNzdjIFx1YjU0YywgJiMzOTs8Y29kZT5hYmNiLWNkPFwvY29kZT4mIzM5OywgJiMzOTs8Y29kZT4tYS1iY2JjZC08XC9jb2RlPiYjMzk7LCAmIzM5Ozxjb2RlPmFiY2QtY2QtPFwvY29kZT4mIzM5O1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgWFx1Yzc1OCBcdWQ2NTVcdWM3YTVcdWM3NzQgXHViNDFjXHViMmU0LiAoXHVhY2Y1XHViYzMxXHVjNzQwICYjMzk7PGNvZGU+LTxcL2NvZGU+JiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjKTxcL3A+XHJcblxyXG48cD5BPHN1Yj4xPFwvc3ViPlx1Yzc0NCBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1Yzc1OCBcdWQ2NTVcdWM3YTVcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBCPHN1Yj4xPFwvc3ViPlx1Yzc0NCBcdWJiMzhcdWM3OTBcdWM1ZjQgQlx1Yzc1OCBcdWQ2NTVcdWM3YTVcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgQTxzdWI+MTxcL3N1Yj5cdWFjZmMgQjxzdWI+MTxcL3N1Yj5cdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzcwXHViOWFjXHViNzgwLCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM3NTggXHVhYzcwXHViOWFjXHViNzgwLCBBU0NJSSBcdWNmNTRcdWI0ZGMgXHVhYzEyXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhY2Y1XHViYzMxXHVhY2ZjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM2NDBcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgS1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzE2XHViMjk0IEE8c3ViPjE8XC9zdWI+XHVhY2ZjIEI8c3ViPjE8XC9zdWI+XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDIwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWFjZmMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSyAmbGU7IDEwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMjY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmxhc3QiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBnaXZlbiB0d28gc3RyaW5ncywgQSBhbmQgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gZXhwYW5zaW9uIG9mIHNvbWUgc3RyaW5nIFggaXMgYSBzdHJpbmcgY3JlYXRlZCBieSBhZGRpbmcgb3IgaW5zZXJ0aW5nIGFueSBudW1iZXIgKHplcm8sIG9uZSBvciBtb3JlKSBvZiBibGFua3MgYW55d2hlcmUgaW4gdGhlIHN0cmluZywgb3IgaW4gdGhlIGJlZ2dpbmluZyBvciB0aGUgZW5kIG9mIHRoZSBzdHJpbmcuIEVnLiwgaWYgdGhlIHN0cmluZyBYIGlzICZsc3F1bzs8Y29kZT5hYmNiY2Q8XC9jb2RlPiZyc3F1bzssIHRoZW4gdGhlIHN0cmluZ3MgJiMzOTs8Y29kZT5hYmNiLWNkPFwvY29kZT4mIzM5OywgJiMzOTs8Y29kZT4tYS1iY2JjZC08XC9jb2RlPiYjMzk7IGFuZCAmIzM5Ozxjb2RlPmFiY2ItY2QtPFwvY29kZT4mIzM5OyBhcmUgZXhwYW5zaW9ucyBvZiB0aGUgc3RyaW5nIFggKGJsYW5rcyBhcmUgZGVub3RlZCBieSB0aGUgY2hhcmFjdGVyICZsc3F1bzs8Y29kZT4tPFwvY29kZT4mbHNxdW87KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SWYgQTxzdWI+MTxcL3N1Yj4gaXMgYW4gZXhwYW5zaW9uIG9mIHRoZSBzdHJpbmcgQSwgYW5kIEI8c3ViPjE8XC9zdWI+IGlzIGFuZCBleHBhbnNpb24gb2YgdGhlIHN0cmluZyBCLCBhbmQgaWYgQTxzdWI+MTxcL3N1Yj4gYW5kIEI8c3ViPjE8XC9zdWI+IGFyZSBvZiB0aGUgc2FtZSBsZW5ndGgsIHRoZW4gd2UgZGVmaW5lIHRoZSBkaXN0YW5jZSBvZiB0aGUgc3RyaW5ncyBBPHN1Yj4xPFwvc3ViPiBhbmQgQjxzdWI+MTxcL3N1Yj4gYXMgdGhlIHN1bSBvZiB0aGUgZGlzdGFuY2VzIG9mIHRoZSBjaGFyYWN0ZXJzIG9uIHRoZSBzYW1lIHBvc2l0aW9ucyBpbiB0aGVzZSBzdHJpbmdzLiBXZSBkZWZpbmUgdGhlIGRpc3RhbmNlIG9mIHR3byBjaGFyYWN0ZXJzIGFzIHRoZSBhYnNvbHV0ZSBkaWZmZXJlbmNlIG9mIHRoZWlyIEFTQ0lJIGNvZGVzLCBleGNlcHQgdGhlIGRpc3RhbmNlIG9mIHRoZSBibGFuayBhbmQgYW5vdGhlciBjaGFyYWN0ZXIsIHdoaWNoIGlzIGdpdmVuIChhbmQgZXF1YWwgZm9yIGFsbCBjaGFyYWN0ZXJzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2ggZmluZHMgdGhlIGV4cGFuc2lvbnMgQTxzdWI+MTxcL3N1Yj4gYW5kIEI8c3ViPjE8XC9zdWI+IG9mIHN0cmluZ3MgQSBhbmQgQiwgdGhhdCBoYXZlIHRoZSBzbWFsbGVzdCBkaWZmZXJlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgdGhlIHN0cmluZyBBLCBhbmQgdGhlIHNlY29uZCBsaW5lIG9mIHN0cmluZyBCLiBUaGV5IGFyZSBjb25zaXN0ZWQgb25seSBvZiBsb3dlciBjYXNlIGNoYXJhY3RlcnMgb2YgdGhlIGVuZ2xpc2ggYWxwaGFiZXQgKGEteiksIGFuZCB0aGUgbnVtYmVyIG9mIGNoYXJhY3RlcnMgaW4gYW55IG9mIHRoZSBzdHJpbmdzIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byAyMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIEssIDEgJmxlOyBLICZsZTsgMTAwLCB0aGUgZGlzdGFuY2Ugb2YgdGhlIGJsYW5rIGFuZCB0aGUgb3RoZXIgY2hhcmFjdGVycy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3Qgb24gb25seSBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIHNob3VsZCBjb25zaXN0IG9mIHRoZSBzbWFsbGVzdCBkaXN0YW5jZSBhcyBkZWZpbmVkIGluIHRoZSB0ZXh0IG9mIHRoZSB0YXNrLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=