【二维一边推2】字符距离

<p class="MsoNormal" style="text-indent: 21pt"><span style="font-family: 宋体">设有字符串<span>X</span>，我们称在<span>X</span>的头尾及中间插入任意多个空格后构成的新字符串为<span>X</span>的扩展串，如字符串<span>X</span>为&ldquo;<span class="SpellE"><span>abcbcd</span></span>&rdquo;，则字符串&ldquo;<span class="SpellE"><span>abcb</span></span>□<span class="SpellE"><span>cd</span></span>&rdquo;，&ldquo;□<span>a</span>□<span class="SpellE"><span>bcbcd</span></span>□&rdquo;和&ldquo;<span class="SpellE"><span>abcb</span></span>□<span class="SpellE"><span>cd</span></span>□&rdquo;都是<span>X</span>的扩展串，这里&ldquo;□&rdquo;代表空格字符。</span></p> <p class="MsoNormal" style="text-indent: 21pt"><span style="font-family: 宋体">如果<span>A1</span>是字符串<span>A</span>的扩展串，<span>B1</span>是字符串<span>B</span>的扩展串，<span>A1</span>与<span>B1</span>具有相同的长度，那么我们定义字符串<span>A1</span>与<span>B1</span>的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的<span>ASCII</span>码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值<span>K</span>，空格字符与空格字符的距离为<span>O</span>。在字符串<span>A</span>、<span>B</span>的所有扩展串中，必定存在两个等长的扩展串<span>A1</span>、<span>B1</span>，使得<span>A1</span>与<span>B1</span>之间的距离达到最小，我们将这一距离定义为字符串<span>A</span>、<span>B</span>的距离。</span></p> <p class="MsoNormal" style="text-indent: 21pt"><span style="font-family: 宋体">请你写一个程序，求出字符串<span>A</span>、<span>B</span>的距离。</span></p>

<p class="MsoNormal" style="text-indent: 21pt"><span style="font-family: 宋体">输入文件第一行为字符串<span>A</span>，第二行为字符串<span>B</span>，<span>A</span>、<span>B</span>均由小写字母组成且长度均不超过<span>2000</span>，第三行为一个整数<span>K</span>，<span>1</span>&le;<span>K</span>&le;<span>100</span>，表示空格与其它字符的距离。</span></p> <p class="MsoNormal" align="left" style="text-align: left; text-indent: 21pt">&nbsp;</p>

<p><span style="font-family: 宋体">输出文件仅一行包含一个整数，表示要求的字符串<span>A</span>、<span>B</span>的距离。</span></p>