#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::map;
using std::set;
using std::bitset;
using std::vector;
using std::string;
using std::multimap;
using std::multiset;
using std::deque;
using std::queue;
using std::stack;
using std::pair;
using std::iterator;

using std::sort;
using std::stable_sort;
using std::reverse;
using std::max_element;
using std::min_element;
using std::unique;
using std::ios_base;
using std::swap;
using std::fill;

using std::setprecision;
using std::fixed;

using std::min;
using std::max;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef string S;

namespace MySpace{

};

#define F(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define fi first
#define se second
#define re return
#define all(x) (x).begin(), (x).end()

ll inq(ll x, ll y, ll mod)
{
    if (y == 0) return 1;
    ll l = inq(x, y / 2, mod);
    if (y % 2) return l * l % mod * x % mod;
    return l * l % mod;
}

ll rev(ll x, ll mod)
{
    return inq(x, mod - 2, mod);
}

inline int nextInt()
{
    int x = 0;
    char c = getchar();
    int mi = (c == '-');
    if (c == '-') c = getchar();
    while ('0' <= c && c <= '9')
    {
        x = 10 * x + c - '0';
        c = getchar();
    }
    if (mi) return x * -1;
    return x;
}

int n, k;
vector<int> c[500000];

struct Node{
    ll x, y;
    ll summ;
    ll sz;
    Node * L, * R;
};

Node * newNode(int x)
{
    Node * a = new Node();
    a->x = x;
    a->y = rand() * (1 << 15) + rand();
    a->summ = x;
    a->sz = 1;
    return a;
}

ll get_summ(Node * b)
{
    if (!b) return 0;
    return b->summ;
}

ll get_sz(Node * b)
{
    if (!b) return 0;
    return b->sz;
}

void Modify(Node * a)
{
    a->summ = a->x + get_summ(a->L) + get_summ(a->R);
    a->sz = 1 + get_sz(a->L) + get_sz(a->R);
}

pair<Node *, Node *> Split(Node * a, int k)
{
    if (a == nullptr) return {nullptr, nullptr};
    if (a->x <= k)
    {
        pair<Node *, Node *> kek = Split(a->R, k);
        a->R = kek.first;
        Modify(a);
        return {a, kek.second};
    }
    else
    {
        pair<Node *, Node *> kek = Split(a->L, k);
        a->L = kek.second;
        Modify(a);
        return {kek.first, a};
    }
}

pair<Node *, Node *> Split2(Node * a, int k)
{
    if (a == nullptr) return {nullptr, nullptr};
    //cout << "too doo" << endl;
    int l = get_sz(a->L);
    if (l < k)
    {
        pair<Node *, Node *> kek = Split2(a->R, k - l - 1);
        a->R = kek.first;
        Modify(a);
        return {a, kek.second};
    }
    else
    {
        pair<Node *, Node *> kek = Split2(a->L, k);
        a->L = kek.second;
        Modify(a);
        return {kek.first, a};
    }
}

Node * Merge(Node * L, Node * R)
{
    if (!L) return R;
    if (!R) return L;
    if (L->y < R->y)
    {
        L->R = Merge(L->R, R);
        Modify(L);
        return L;
    }
    else
    {
        R->L = Merge(L, R->L);
        Modify(R);
        return R;
    }
}

void add(int x, Node *& Root)
{
    Node * Nd = newNode(x);
    pair<Node *, Node *> g = Split(Root, x - 1);
    g.first = Merge(g.first, Nd);
    Root = Merge(g.first, g.second);
}

ll get(int r, Node *& Root)
{
    //cout << "kak" << endl;
    pair<Node *, Node *> Nd = Split2(Root, r);
    //cout << "paw" << endl;
    ll x = get_summ(Nd.first);
    //cout << "Milliarde" << endl;
    //cout << ": " << r << " " << get_sz(Nd.first) << endl;
    Root = Merge(Nd.first, Nd.second);
    return x;
}

void describe(Node * Root)
{
    if (!Root) return;
    describe(Root->L);
    cout << "(" << Root->summ << " " << Root->x << " " << Root->y << ") ";
    describe(Root->R);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Node * Root = nullptr;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        c[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)
    {
        sort(all(c[i]));
        reverse(all(c[i]));
    }
    sort(c + 1, c + n + 1);
    reverse(c + 1, c + n + 1);
    ll ans = 0;
    ll cur = 0;
    ll r = 0;
    int others = k;
    for (int t = 1; t <= n; t++)
    {
        if (c[t].size() > 0)
        {
            others--;
            r++;
            cur += c[t][0];
            for (int j = 1; j < c[t].size(); j++)
            {
                //cout << "added " << -c[t][j] << endl;
                add(-c[t][j], Root);
            }
            //describe(Root);
            //cout << endl;
            if (others >= 0)
            {
                ans = max(ans, r * r + cur - get(others, Root));
            }
        }
    }
    cout << ans;
}


Measured memory_bytes: 18432