解题思路

先把题目里的“交换”单独看。

设第 $i$ 位上的两个数字分别为 $a_i,b_i$，并且题目保证 $a_i\ne b_i$。 无论是否交换，这一位对两个数差值的“绝对贡献”都只和

题目内容

小明有两个位数为$n$的数$x$和$y$，这两个数在相同数位上的数字互不相同。小明可以对这 两个数执行如下两种操作

(1)交换损作：交换$x$和$y$某一数位上的数字

(2)删除操作：删除$x$和$y$某一数位，然后分别将剩余的数位拼接。删除操作后允许数存在前导零(即数位的前几位可以是$0$)，删除操作不能删除最低位

例如，对于数$x=3561$和$y=7812$，对最高位执行交换操作后，$x=7561,y=3812$；再对次高位执行删除操作后，$x=761,y=312$交换操作可以执行任意次。请你计算删除操作执行不超过$k$次的情况下，两个数的差的绝对值最小是多少。

输入描述

输入第一行有两个整数$n(2≤n≤10^3)和k(1≤k<n)$，分别表示两个数的位数以及删除操作最多执行次数。

第二行有两个数$x$和$y(10^{n-1}≤x,y<10^n)$，表示题目给定的两个数。

保证两个数在同一数位上的数字不同。

输出描述

输出一个整数，表示经过任意次交换操作、不超过$k$次删除操作后，两个数的差的绝对值的最小值。

样例1

输入

6 2
329304
878189

输出

715

说明

分别对第一位、第二位执行删除操作，对剩余的数字执行交换操作，最终两个数字变为$9104$ 和$8389$，差的绝对值为 $715$。