#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n,ans,maxn,a[10001];
string s;
ull max(ull t1,ull t2){
	if(t1>t2)return t1;
	return t2;
}
int main(){
	cin>>s;
	scanf("%lld",&n);
	ull l=s.size();
	if(n<=l){
		printf("0\n");
		return 0;
	}
	for(ull i=0;i<l;i++)a[s[i]]++,maxn=max(maxn,a[s[i]]);
	while(1){
		if(n-l<=maxn){
			ans++;
			break;
		}
		l+=maxn;
		maxn<<=1;
		ans++;
	}
	printf("%lld",ans);
	return 0;
}