using namespace std;
const int N=10000;
int n[N],m[N];
string s[N];
int main()
{
	int a,b,sum=1,num=1,h=0;
	string p,o;
	cin>>a>>b;
	for(int i=0;i<a;i++)
		cin>>s[i]>>n[i];
	for(int i=1;i<a;i++)
	{
		for(int u=a-1;u>0;u--)
		{
			if(n[u]>n[u-1])
			{
				swap(n[u],n[u-1]);
				swap(s[u],s[u-1]);
			}
		}
	}
	for(int i=0;i<a;i++)
	{
		if(n[i]!=n[i+1])
		{
			m[i]=sum;
			if(sum<=b)
			h++;
			sum++;
			num++;
			if(sum<num)
			sum=num;
		}
		else if(n[i]==n[i+1])
		{
			m[i]=sum;
			num++;
			if(sum<=b)
			h++;
		}
	}
	for(int u=1;u<=100;u++)
	{
	    for(int i=0;i<a;i++)
	  {
		if(m[i]==m[i+1])
		{
		    o=s[i];
		    p=s[i+1];
		    int len1=o.length(),len2=p.length();
		    for(int k=0;k<len1-1;k++)
		    {
		    	int g=o[k],x=p[k];
	           if(g<x)
			   break;
			   else if(g>x) 
			   {
			   	swap(s[i],s[i+1]);
			   	break;
			   }
			}
		}
  	  }
}
    for(int i=0;i<a;i++)
    {
    	cout<<m[i]<<":"<<s[i]<<endl;
	}
	cout<<h;
	return 0;
}