#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N,K;
    cin>>N>>K;
    long long int lis[11][2003],lissize[11]={0};
    for(int i=0;i<11;i++){
        for(int j=1;j<2003;j++)lis[i][j]=-2000000000;
    }
    for(int i=0;i<N;i++){
        int a,b;
        cin>>a>>b;
        lis[b][lissize[b]+1]=a;
        lissize[b]++;
    }
    for(int i=0;i<11;i++){
        sort(lis[i]+1,lis[i]+2003);
        reverse(lis[i]+1,lis[i]+2003);
    }
    for(int i=0;i<11;i++){
        for(int j=1;j<2003;j++)lis[i][j]+=lis[i][j-1]+(j-1)*2;
    }
    /*
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            if(0<=lis[i][j])printf("[%lld]",lis[i][j]);
        }
        puts("");
    }
    */
    long long int fie[13][4003]={0};
    for(int i=0;i<10;i++){
        for(int j=0;j<2001;j++){
            for(int k=0;k<2001;k++){
                if(j+k<=2000)fie[i+1][j+k]=max(fie[i+1][j+k],fie[i][j]+lis[i+1][k]);
            }
        }
    }
    cout<<fie[10][K]<<endl;
    return 0;
}