using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    static class DicExt
    {
        public static V GetOrInit<K, V>(this IDictionary<K, V> dic, K key) where V : new()
        {
            V val;
            if (dic.TryGetValue(key, out val))
                return val;

            val = new V();
            dic.Add(key, val);
            return val;
        }
    }
    struct Sushi
    {
        public int kind;
        public int delicious;
        public Sushi(int kind, int delicious)
        {
            this.kind = kind;
            this.delicious = delicious;
        }

        public override string ToString() => $"({kind}, {delicious})";
    }
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt32();
            var N = line[0];
            var K = line[1];

            var sushi = consoleReader.RepeatSplitInt32(N).Select(l => new Sushi(l[0], l[1])).OrderByDescending(s => s.delicious).ToArray();

            var result = sushi.Take(K).ToArray();
            long sum = 0;
            var kindCount = new Dictionary<int, int>();
            foreach (var item in result)
            {
                kindCount[item.kind] = kindCount.GetOrInit(item.kind) + 1;
                sum += item.delicious;
            }
            var point = (long)kindCount.Count * kindCount.Count + sum;

            var k = K;
            for (int i = K - 1; i >= 0; i--)
            {
                if (kindCount[sushi[i].kind] > 1)
                {
                    kindCount[sushi[i].kind]--;
                    sum -= sushi[i].delicious;

                    while (k < N && kindCount.ContainsKey(sushi[k].kind)) k++;
                    if (k >= N) break;
                    kindCount[sushi[k].kind] = 1;
                    sum += sushi[k].delicious;

                    var tmp = (long)kindCount.Count * kindCount.Count + sum;
                    if (point < tmp) point = tmp;
                }
            }

            return point;
        }

        const int mod = 1000000007;
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
    }

    public class ConsoleReader
    {
        public virtual string String() => Console.ReadLine();
        public int Int32() => int.Parse(String());
        public long Int64() => long.Parse(String());
        public ulong UInt64() => ulong.Parse(String());
        public double Double() => double.Parse(String());
        public string[] Split() => String().Split().ToArray();
        public int[] SplitInt32() => String().Split().Select(int.Parse).ToArray();
        public long[] SplitInt64() => String().Split().Select(long.Parse).ToArray();
        public ulong[] SplitUInt64() => String().Split().Select(ulong.Parse).ToArray();
        public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray();

        public IEnumerable<string> Repeat(int count)
        {
            for (int i = 0; i < count; i++)
                yield return String();
        }
        public IEnumerable<int> RepeatInt32(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Int32();
        }
        public IEnumerable<long> RepeatInt64(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Int64();
        }
        public IEnumerable<string[]> RepeatSplit(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Split();
        }
        public IEnumerable<int[]> RepeatSplitInt32(int count)
        {
            for (int i = 0; i < count; i++)
                yield return SplitInt32();
        }
    }
}


Measured memory_bytes: 28084