문제
어떤 문자열 X의 확장이란 그 문자열의 어떤 위치 또는 가장 앞과 뒤에 공백을 임의의 개수(0, 1또는 그 이상)만큼 추가하는 것이다. 예를 들어, 문자열 X가 'abcbcd'일 때, 'abcb-cd', '-a-bcbcd-', 'abcd-cd-'는 문자열 X의 확장이 된다. (공백은 '-'로 표시)
A1을 문자열 A의 확장이라고 하고, B1을 문자열 B의 확장이라고 했을 때, A1과 B1의 길이가 같다면, 두 문자열의 거리를 정의할 수 있다. 두 문자열의 거리란, 같은 위치에서 문자의 거리의 합이다. 문자의 거리란, ASCII 코드 값의 차이를 말한다. 이 때, 공백과 다른 문자와의 차이는 입력으로 주어지는 K이다.
두 문자열 A와 B가 주어졌을 때, 가장 짧은 거리를 갖는 A1과 B1을 찾는 프로그램을 작성하시오.
W3sicHJvYmxlbV9pZCI6IjMyNjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVkNjU1XHVjN2E1XHVhY2ZjIFx1YWM3MFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBYXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc4MCBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM3MDRcdWNlNTggXHViNjEwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NWVcdWFjZmMgXHViNGE0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWM3ODRcdWM3NThcdWM3NTggXHVhYzFjXHVjMjE4KDAsIDFcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMSlcdWI5Y2NcdWQwN2MgXHVjZDk0XHVhYzAwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjNzkwXHVjNWY0IFhcdWFjMDAgJiMzOTthYmNiY2QmIzM5O1x1Yzc3YyBcdWI1NGMsICYjMzk7YWJjYi1jZCYjMzk7LCAmIzM5Oy1hLWJjYmNkLSYjMzk7LCAmIzM5O2FiY2QtY2QtJiMzOTtcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFhcdWM3NTggXHVkNjU1XHVjN2E1XHVjNzc0IFx1YjQxY1x1YjJlNC4gKFx1YWNmNVx1YmMzMVx1Yzc0MCAmIzM5Oy0mIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGMpPFwvcD5cclxuXHJcbjxwPlxyXG5cdEExXHVjNzQ0IFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIEIxXHVjNzQ0IFx1YmIzOFx1Yzc5MFx1YzVmNCBCXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBBMVx1YWNmYyBCMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzE5XHViMmU0XHViYTc0LCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3ODAsIFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3ODAsIEFTQ0lJIFx1Y2Y1NFx1YjRkYyBcdWFjMTJcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhY2Y1XHViYzMxXHVhY2ZjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM2NDBcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgS1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzE2XHViMjk0IEExXHVhY2ZjIEIxXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDIwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWFjZmMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSyAmbGU7IDEwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmxhc3QiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBnaXZlbiB0d28gc3RyaW5ncywgQSBhbmQgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gZXhwYW5zaW9uIG9mIHNvbWUgc3RyaW5nIFggaXMgYSBzdHJpbmcgY3JlYXRlZCBieSBhZGRpbmcgb3IgaW5zZXJ0aW5nIGFueSBudW1iZXIgKHplcm8sIG9uZSBvciBtb3JlKSBvZiBibGFua3MgYW55d2hlcmUgaW4gdGhlIHN0cmluZywgb3IgaW4gdGhlIGJlZ2dpbmluZyBvciB0aGUgZW5kIG9mIHRoZSBzdHJpbmcuIEVnLiwgaWYgdGhlIHN0cmluZyBYIGlzICZsc3F1bzthYmNiY2QmcnNxdW87LCB0aGVuIHRoZSBzdHJpbmdzICYjMzk7YWJjYi1jZCYjMzk7LCAmIzM5Oy1hLWJjYmNkLSYjMzk7IGFuZCAmIzM5O2FiY2ItY2QtJiMzOTsgYXJlIGV4cGFuc2lvbnMgb2YgdGhlIHN0cmluZyBYIChibGFua3MgYXJlIGRlbm90ZWQgYnkgdGhlIGNoYXJhY3RlciAmbHNxdW87LSZsc3F1bzspLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiBBMSBpcyBhbiBleHBhbnNpb24gb2YgdGhlIHN0cmluZyBBLCBhbmQgQjEgaXMgYW5kIGV4cGFuc2lvbiBvZiB0aGUgc3RyaW5nIEIsIGFuZCBpZiBBMSBhbmQgQjEgYXJlIG9mIHRoZSBzYW1lIGxlbmd0aCwgdGhlbiB3ZSBkZWZpbmUgdGhlIGRpc3RhbmNlIG9mIHRoZSBzdHJpbmdzIEExIGFuZCBCMSBhcyB0aGUgc3VtIG9mIHRoZSBkaXN0YW5jZXMgb2YgdGhlIGNoYXJhY3RlcnMgb24gdGhlIHNhbWUgcG9zaXRpb25zIGluIHRoZXNlIHN0cmluZ3MuIFdlIGRlZmluZSB0aGUgZGlzdGFuY2Ugb2YgdHdvIGNoYXJhY3RlcnMgYXMgdGhlIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgdGhlaXIgQVNDSUkgY29kZXMsIGV4Y2VwdCB0aGUgZGlzdGFuY2Ugb2YgdGhlIGJsYW5rIGFuZCBhbm90aGVyIGNoYXJhY3Rlciwgd2hpY2ggaXMgZ2l2ZW4gKGFuZCBlcXVhbCBmb3IgYWxsIGNoYXJhY3RlcnMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBmaW5kcyB0aGUgZXhwYW5zaW9ucyBBMSBhbmQgQjEgb2Ygc3RyaW5ncyBBIGFuZCBCLCB0aGF0IGhhdmUgdGhlIHNtYWxsZXN0IGRpZmZlcmVuY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb25zaXN0cyBvZiB0aGUgc3RyaW5nIEEsIGFuZCB0aGUgc2Vjb25kIGxpbmUgb2Ygc3RyaW5nIEIuIFRoZXkgYXJlIGNvbnNpc3RlZCBvbmx5IG9mIGxvd2VyIGNhc2UgY2hhcmFjdGVycyBvZiB0aGUgZW5nbGlzaCBhbHBoYWJldCAoYS16KSwgYW5kIHRoZSBudW1iZXIgb2YgY2hhcmFjdGVycyBpbiBhbnkgb2YgdGhlIHN0cmluZ3MgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDIwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnNpc3RzIG9mIGFuIGludGVnZXIgSywgMSAmbGU7IEsgJmxlOyAxMDAsIHRoZSBkaXN0YW5jZSBvZiB0aGUgYmxhbmsgYW5kIHRoZSBvdGhlciBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBvbiBvbmx5IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgc2hvdWxkIGNvbnNpc3Qgb2YgdGhlIHNtYWxsZXN0IGRpc3RhbmNlIGFzIGRlZmluZWQgaW4gdGhlIHRleHQgb2YgdGhlIHRhc2suJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d
