#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K, class V> using Umap = gp_hash_table<K, V>;
using Trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;

inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};

signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout.setf(ios_base::fixed);
    cout.precision(10);

    int k, n;
    cin >> n >> k;

    vector<int> t(n), d(n);

    rep(i,n){
        cin >> t[i] >> d[i];
        --t[i];
    }

    vector<int> v(n);
    iota(all(v), 0);

    sort(all(v), [&](int a, int b){
        return (d[a] > d[b]);
    });

    vector<min_heap<int> > vec(n);
    set<pair<int, int> > s;
    int cnt = 0, sum = 0;

    rep(i,k){
        if(vec[t[v[i]]].empty()) ++cnt;
        else{
            s.erase({vec[t[v[i]]].top(), t[v[i]]});
        }
        sum += d[v[i]];
        vec[t[v[i]]].emplace(d[v[i]]);
        if(vec[t[v[i]]].size() > 1){
            s.insert({vec[t[v[i]]].top(), t[v[i]]});
        }
    }

    int res = 0;
    chmax(res, sum + cnt * cnt);

    for(int i = k; i < n; ++i){
        if(!vec[t[v[i]]].empty()) continue;
        if(s.empty()) break;

        auto [value, index] = *s.begin();
        sum -= value;
        sum += d[v[i]];
        s.erase(s.begin());

        vec[index].pop();
        if(vec[index].size() > 1){
            s.insert({vec[index].top(), index});
        }

        vec[t[v[i]]].emplace(d[v[i]]);
        ++cnt;

        chmax(res, sum + cnt * cnt);
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 12444