#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int ans=9999999;
char f[44444];
int size;int n,m;
int g[44444]={};int weizhi;
struct ff{int x,y,num;}cnt[11]={};
bool cmp1(ff m,ff n){return m.y<n.y||(m.y==n.y&&m.num>n.num);}
bool cmp2(ff m,ff n){return m.num<n.num;}
int abs(int a){return a>=0?a:-a;}
void check(int s)
{
	for(int i=0;i<=9;i++)
		cnt[i].y=abs(s-i);
	sort(cnt,cnt+10,cmp1);
	int te=m,temp=0;
	for(int i=0;i<=9;i++)
	{
		if(cnt[i].x>te)
			{temp+=te*cnt[i].y;break;}
		else
			te-=cnt[i].x,temp+=cnt[i].y*cnt[i].x;
	}
	if(temp<ans)
		ans=temp,weizhi=s;
	sort(cnt,cnt+10,cmp2);
}
int main()
{
	freopen("fancy.in","r",stdin);
	freopen("fancy.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%s",f);
	size=strlen(f);
	for(int i=0;i<size;i++)
		g[i]=f[i]-'0';
	for(int i=0;i<=9;i++)
		cnt[i].num=i;
	for(int i=0;i<size;i++)
		cnt[g[i]].x++;
	for(int i=0;i<=9;i++)
		check(i);
	printf("%d\n",ans);
	for(int i=0;i<=9;i++)
		cnt[i].y=abs(weizhi-i);
	sort(cnt,cnt+10,cmp1);int cnt2=0;
	for(int i=0;i<=9;i++)
	{
		int te=cnt[i].num;
		if(te>weizhi)
			for(int i=0;i<size;i++)
			{
				if(cnt2>=m)
					break;
				if(g[i]==te)
					g[i]=weizhi,cnt2++;
			}
		else
		{
			for(int i=size-1;i>=0;i--)
			{
				if(cnt2>=m)
					break;
				if(g[i]==te)
					g[i]=weizhi,cnt2++;
			}
		}
		if(cnt2>=m)break;
	}
	for(int i=0;i<size;i++)
		printf("%d",g[i]);
	printf("\n");
}