using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace PaizaSkillCheck
{
    public class Program
    {
        public static void Main(string[] args)
        {
            string[] line = Console.ReadLine().Split(' ');
            int n = int.Parse(line[0]);
            int k = int.Parse(line[1]);

            //  最大ポイント
            ulong maxPoint = 0;

            //  選択中の寿司の合計ポイント
            ulong nowPoint = 0;

            //  選択中の寿司の種類           
            int kindCount = 0;

            //  各種の最大寿司
            Sushi[] topSushi = new Sushi[n + 1];

            //  すべての寿司を取得
            List<Sushi> sushiList = new List<Sushi>(n);
            for (int i = 0; i < n; i++)
            {
                line = Console.ReadLine().Split(' ');
                int kind = int.Parse(line[0]);
                int point = int.Parse(line[1]);

                Sushi sushi = new Sushi(kind, point);

                topSushi[kind] = Sushi.Max(topSushi[kind], sushi);

                sushiList.Add(sushi);
            }
            //  寿司を降順ソート
            List<Sushi> selectList = sushiList.OrderByDescending(i => i.isFirst).OrderByDescending(i => i.point).Take(k).ToList();

            //  その種類の中で一番大きなポイントの寿司
            List<Sushi> isFirstList = topSushi.Where((a) => a != null).OrderByDescending(i => i.point).ToList();

            //  逆転させる
            selectList.Reverse();

            //  いらない寿司
            Sushi[] unnecessary = new Sushi[k];
            int unnecessary_index = 0;
            foreach (Sushi sushi in selectList)
            {
                //  選択中の寿司の合計ポイントを数える
                nowPoint += (ulong) sushi.point;

                //  選択中の寿司の種類を数える
                if (sushi.isFirst)
                {
                    kindCount++;
                }
                //  いらない寿司順に配列に格納する
                else
                {
                    unnecessary[unnecessary_index] = sushi;
                    unnecessary_index++;
                }
            }
            unnecessary_index = 0;

            maxPoint = nowPoint + ((ulong) kindCount * (ulong) kindCount);

            for (int i = (kindCount + 1); i <= k; i++)
            {
                nowPoint -= (ulong) unnecessary[unnecessary_index].point;
                unnecessary_index++;

                if (isFirstList.Count < i)
                {
                    Console.WriteLine(maxPoint);
                    Console.ReadLine();
                    return;
                }
                nowPoint += (ulong) isFirstList[i - 1].point;

                maxPoint = Math.Max(maxPoint, nowPoint + ((ulong)i * (ulong)i));
            }

            Console.WriteLine(maxPoint);
            Console.ReadLine();
        }

        /// <summary>
        /// 寿司オブジェクト
        /// </summary>
        public class Sushi : IComparable
        {
            public int kind;
            public int point;
            public bool isFirst;

            public Sushi(int kind, int point)
            {
                this.kind = kind;
                this.point = point;
            }

            public override string ToString()
            {
                return string.Format("Kind : {0}, Point : {1}", kind, point);
            }

            public int CompareTo(Object obj)
            {
                Sushi sushi = (Sushi) obj;

                return (sushi?.point ?? 0) - this.point;
            }

            public static Sushi Max(Sushi a, Sushi b)
            {
                if (a == null)
                {
                    if (b != null) b.isFirst = true;
                    return b;
                }
                if (b == null)
                {
                    if (a != null) a.isFirst = true;
                    return a;
                }

                bool largeA = (a.point > b.point);

                if(largeA)
                {
                    a.isFirst = true;
                    b.isFirst = false;

                    return a;
                }
                else
                {
                    a.isFirst = false;
                    b.isFirst = true;

                    return b;
                }
            }
        }
    }
}


Measured memory_bytes: 32064