#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
template<typename T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; // find_by_order(), order_of_key()
using ll = long long int;
using i64 = long long int;
#define all(vec) (vec).begin(),(vec).end()
template <typename T> inline void ckmax(T &x, T y) {if (y > x) x = y; }
template <typename T> inline void ckmin(T &x, T y) {if (y < x) x = y; }
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " =: " << a << endl;
    err(++it, args...);
}
template <typename T1, typename T2>
inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& buf) {
    return os << "(" << buf.first << ": " << buf.second << ")";
}
template<typename T>
inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v) {
    bool first = true;
    os << "[";
    for(unsigned int i = 0; i < v.size(); i++) {
        if(!first) os << ", ";
        os << v[i];
        first = false;
    }
    return os << "]";
}
template<typename T>
inline std::ostream &operator << (std::ostream & os,const multiset<T>& v) {
    bool first = true;
    os << "{";
    for (auto ii = v.begin(); ii != v.end(); ++ii) {
        if(!first) os << ", ";
        os << *ii;
        first = false;
    }
    return os << "}";
}
inline std::ostream &operator << (std::ostream & os,const std::multiset<pair<int,int>,greater<pair<int,int>>>& v) {
    bool first = true;
    os << "{";
    for (auto x: v) {
        if(!first) os << ", ";
        os << x;
        first = false;
    }
    return os << "}";
}
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v) {
    bool first = true;
    os << "{";
    for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
        if(!first) os << ", ";
        os << *ii ;
        first = false;
    }
    return os << "}";
}
template<typename T>
inline std::ostream &operator << (std::ostream & os,const vector<vector<T>>& v) {
    for (auto &u: v) os << '\n' << u;
    return os;
}
template<typename T>
void finish(T ans) {cout << ans << '\n'; exit(0);}
const int MOD = 1e9 + 7;
const long long INF = 1e18;
const double EPS = 1e-6;
#define PI 3.14159265358979323846
#define sz(v) (int((v).size()))
/***********************************************************************/

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n, -MOD);
    multiset<pair<int,int>,greater<pair<int,int>>> st;
    for (int i = 0; i < n; ++i) {
        int t, d;
        cin >> t >> d;
        --t;
        a[t] = max(a[t], d);
        st.emplace(d, t);
    }
    vector<int> t(n);
    iota(all(t), 0);
    sort(all(t), [&] (const auto &x, const auto &y) {
        return a[x] > a[y];
    });
    i64 base = 0LL, sum = 0;
    base = a[t[0]];
    st.erase(st.find({a[t[0]], t[0]}));
    multiset<pair<int,int>> used;
    int cnt = 1;
    while (cnt < k) {
        //~ assert(sz(st));
        auto p = *st.begin();
        sum += p.first;
        st.erase(st.begin());
        used.insert(p);
        ++cnt;
    }
    i64 ans = base + sum + 1;
    for (int ii = 2; ii <= k; ++ii) {
        int i = t[ii - 1];
        if (a[i] == -MOD) break;
        base += a[i];
        if (used.count({a[i], i})) {
            sum -= a[i];
            used.erase({a[i], i});
        } else {
            //~ assert(st.count({a[i], i}));
            st.erase({a[i], i});
            sum -= used.begin()->first;
            used.erase(used.begin());
        }
        i64 cur = base + sum + (long long) ii * ii;
        ans = max(ans, cur);
    }
    cout << ans << '\n';
    
    return 0;
}


Measured memory_bytes: 5760