class in{struct my_iterator{int it;const bool rev;explicit constexpr my_iterator(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(my_iterator& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const my_iterator i,n;public:explicit constexpr in(int n):i(0),n(n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const my_iterator& begin(){return i;}const my_iterator& end(){return n;}};

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, k; cin >> n >> k;
    vector<vector<int>> books(10);
    for(int _ : in(n)) {
        int c, g;
        cin >> c >> g;
        --g;
        books[g].emplace_back(c);
    }
    vector<i64> dp(k + 1, -1e12);
    dp[0] = 0LL;
    for(auto& book : books) {
        sort(book.rbegin(), book.rend());
        i64 sum = 0;
        auto dp_ = dp;
        for(i64 i : in(book.size())) {
            sum += book[i];
            for(int j : in(k + 1)) if(dp[j] >= 0) {
                int x = i + 1 + j;
                if(x > k) continue;
                dp_[x] = max(dp_[x], dp[j] + sum + i * (i + 1));
            }
        }
        dp = dp_;
    }
    cout << dp[k] << endl;
    return 0;
}