using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var (N, K) = Slice2<long>();
            var td = new List<(long t, long d)>();
            for (var i = 0; i < N; ++i)
                td.Add(Slice2<long>());
            td.Sort((l, r) => r.d.CompareTo(l.d));//降順
            var used = new priority_queue<(long t, long d)>((l, r) => r.d.CompareTo(l.d));
            var kanri = new Dictionary<long, long>();//type,num
            var rems = new List<(long t, long d)>();
            var maxSum = 0L;
            //各種類の最大値を使用する
            foreach (var t in td)
            {
                if (used.num < K && !kanri.ContainsKey(t.t))
                {
                    kanri[t.t] = 1;
                    used.insert(t);
                    maxSum += t.d;
                }
                else
                    rems.Add(t);
            }
            rems.Reverse();//昇順
            //種類がK未満の場合、大きいのを使ってK個まで埋める
            while (used.num < K)
            {
                var le = rems.Last();
                rems.RemoveAt(rems.Count - 1);
                ++kanri[le.t];
                used.insert(le);
                maxSum += le.d;
            }
            //初期値
            var dp = maxSum + (long)kanri.Count * (long)kanri.Count;
            while (rems.Any())
            {
                //最小のものを1個捨てる
                var e = used.extract();
                //残りから最大のものを1個食べる
                var le = rems.Last();
                //交換しても意味ないので終了
                if (le.d <= e.d) break;
                used.insert(le);
                maxSum += le.d - e.d;
                ++kanri[le.t];
                --kanri[e.t];
                if (0 == kanri[e.t]) kanri.Remove(e.t);
                dp = Max(dp, maxSum + (long)kanri.Count * (long)kanri.Count);
                rems.RemoveAt(rems.Count - 1);
            }
            WriteLine(dp);
        }
        class priority_queue<T>
        {
            Comparison<T> cmp;
            T[] A = new T[2000000];
            // var pq = new priority_queue<long>((l, r) => l.CompareTo(r));
            // とすれば値の大きいものから優先
            public priority_queue(Comparison<T> c)
            {
                cmp = c;
            }
            public int num { get; private set; } = 0;
            public void insert(T v)
            {
                A[num] = v;
                ++num;
                increaseKey(num);
            }
            void increaseKey(int i)
            {
                while (1 < i && 0 < cmp(A[i - 1], A[i / 2 - 1]))
                {
                    var t = A[i - 1];
                    A[i - 1] = A[i / 2 - 1];
                    A[i / 2 - 1] = t;
                    i = i / 2;
                }
            }
            public T extract()
            {
                if (num < 1) return default(T);
                var max = A[0];
                A[0] = A[num - 1];
                --num;
                maxHeapify(1);
                return max;
            }
            void maxHeapify(int i)
            {
                var H = num;
                var l = left(i);
                var r = right(i);
                var largest = 0;
                if (l <= H && 0 < cmp(A[l - 1], A[i - 1])) { largest = l; } else { largest = i; }
                if (r <= H && 0 < cmp(A[r - 1], A[largest - 1])) { largest = r; }
                if (largest != i)
                {
                    var t = A[i - 1];
                    A[i - 1] = A[largest - 1];
                    A[largest - 1] = t;
                    maxHeapify(largest);
                }
            }
            int left(int l) => l * 2;
            int right(int r) => r * 2 + 1;
        }


        static long Mod = 998244353;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

Measured memory_bytes: 55072