#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P,P> PP;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, k;
    vector<ll> book[10];
    cin >> n >> k;
    REP(i,n){
        ll c, g;
        cin >> c >> g;
        g--;
        book[g].push_back(c);
    }
    REP(i,10){
        SORT(book[i]);
        book[i].push_back(0);
        reverse(ALL(book[i]));
        REP(j,book[i].size()-1){
            book[i][j+1] += book[i][j];
        }
    }
    ll dp[15][4005]{}; // i種類までみてj本選んだときの最大
    REP(i,10){
        REP(j,k+1){
            if(j>0&&dp[i][j]==0)break;
            REP(m,book[i].size()){
                dp[i+1][j+m] = max(dp[i+1][j+m],dp[i][j]+book[i][m]+(m-1)*m);
            }
        }
    }
    cout << dp[10][k] << endl;
    return 0;
}

