#include<cstdio>
#include<iostream>
using namespace std;
const int N=10010;
int n,k,mn=100000010,ans;
char s[N];
int c[N],a[N],b[N],num[N];
int main(){
	freopen("fancy.in","r",stdin);
	freopen("fancy.out","w",stdout);
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)b[i]=a[i]=s[i]-'0',num[a[i]]++;
	for(int i=0;i<=9;i++){
		ans=0;
		for(int j=1;j<=n;j++) b[j]=a[j];
		if(num[i]>=k){printf("0\n");for(int i=1;i<=n;i++) printf("%d",a[i]);return 0;}
		else{
			int p=i-1,q=i+1,tmp=k-num[i],tmp1=k-num[i];
			for(int j=1;j<=10&&(q<10||p>=0);j++){
				if(q<10){
					for(int k=1;k<=n&&tmp;k++) 
					if(b[k]==q) b[k]=i,tmp--;
					ans+=min(tmp1,num[q])*(q-i);tmp1=tmp;
					q++;
				}
				if(p>=0){
					for(int k=1;k<=n&&tmp;k++) if(b[k]==p) b[k]=i,tmp--;
					ans+=min(tmp1,num[p])*(i-p);tmp1=tmp;
					p--;
				}
			}
			if(ans<mn){
				mn=ans;
				for(int i=1;i<=n;i++)c[i]=b[i];
			}
		}
	}
	printf("%d\n",mn);
	for(int i=1;i<=n;i++) printf("%d",c[i]);
}