#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cnt = 1,mc,tf = 1,num;//ans是最后有多少个人拿到奶茶,cnt计数用的,mc是名次,tf是同等分数的人
struct P{
    string name;
   int id,score;
}people[10000];
bool cmp(P p1,P p2){//先判断分数是否相同
    if(p1.score!=p2.score) return p1.score>p2.score;//若可以比较直接返回
    else return p1.name<p2.name;//同分则比较字母序
}
int main(){
    cin >> m >> n;
    for(int i=1;i<=m;i++)
        cin>>people[i].name>>people[i].score;
    sort(people+1,people+m+1,cmp);
    while(cnt<=m)
    {   //最开始的people[0].score = 0
        if(people[cnt].score == people[cnt - 1].score)//如果和上一个分数相同，同分人数+1,能喝到奶茶的人+1，同时记录该人的名次
        {
            tf ++;
            num++;//喝奶茶的人数
            people[cnt].id = mc;
        }else{//如果不同，名次加上上一次同分的人数，同时新的分数的人为1而不是0，记录该人名次
            mc += tf;
            people[cnt].id = mc;
            tf = 1;
            if(mc > n && ans == 0)ans = num;//判断现在的名次是否超过n，如果超过，此时num喝奶茶的人数还没有+1，已经不满足条件，直接记录答案
            num ++;//至于ans == 0这个条件可以手动去掉找不同，和我的循环方式有关
        }
        ++cnt;//计数器+1
    }
    for(int i=1;i<=m;i++)
        cout<<people[i].id<<":"<<people[i].name<<endl;
    cout << ans;
    return 0;
}