#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
typedef pair<int, int> pii;

int main(){
    int n,k;
    cin >> n >> k;
    vector<vector<int>> val_pre(10);
    for(int i=0; i<n; i++){
        int v,g;
        cin >> v >> g;
        val_pre[g-1].push_back(v);
    }
    vector<int> dp(k+1, 0);
    for(int i=0; i<10; i++){
        sort(val_pre[i].begin(), val_pre[i].end(), greater<int>());
        vector<int> v(k+1, 0);
        int curr = 0;
        for(int j=0; j<min(k, (int)val_pre[i].size()); j++){
            curr += val_pre[i][j];
            v[j+1] = curr +j*(j+1);
        }
        for(int j=k; j>=0; j--){
            for(int s=0; s<=j; s++){
                dp[j] = max(dp[j], dp[s]+v[j-s]);
            }
        }
    }
    cout << dp[k] << endl;
    return 0;
}

