using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Runtime.CompilerServices;

public class Contest
{
	static void Swap<T>(ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; }
	public const long MOD1 = 1000000007L; // 10^9+7

	public static void Main() {
        int n,k;
		VT<int,int>[] tdl;
		MyIO.ReadMulti(out n, out k);
		MyIO.ReadLines(n, out tdl);

		Array.Sort(tdl,(x,y)=>y.Item2-x.Item2);
		bool[] used = new bool[n];

		List<VT<int,int>> li = new List<VT<int, int>>();
		Dictionary<int,int> kind = new Dictionary<int, int>();
		long sumd = 0;
		for (int i = 0; i < n; i++) {
			if(!kind.ContainsKey(tdl[i].Item1)&&(li.Count<k)){
				li.Add(tdl[i]);
				kind.Add(tdl[i].Item1,1);
				sumd += tdl[i].Item2;
				used[i] = true;
			}
		}

		PriorityQueue<VT<int,int>> que2 = new PriorityQueue<VT<int,int>>((x,y)=>y.Item2-x.Item2);
		for (int i = 0; i < n; i++) if(!used[i]) que2.Enqueue(tdl[i]);
		while ((li.Count<k)&&(0<que2.Count)) {
			var q = que2.Dequeue();
			li.Add(q);
			kind[q.Item1]++;
			sumd += q.Item2;
		}

		li.Sort((x,y)=>x.Item2-y.Item2);

		bool update = true;
		while(update){
			update = false;
			for(int j=0;j<li.Count;j++) {
				var e = li[j];
				if((kind[e.Item1]==1) && (0<que2.Count) && ((que2.Peek().Item2-e.Item2-2*kind.Count+1)>0)){
					var q = que2.Dequeue();
					li.Add(q);
					sumd += q.Item2-e.Item2;
					li.RemoveAt(j);
					kind.Remove(e.Item1);
					update = true;
					break;
				}
			}
		}
 
		MyIO.WriteMulti(sumd+(long)kind.Count*(long)kind.Count);
 
 
 
		
	}

 

 
 
 
}
 


public class PriorityQueue<T>
{
    private readonly List<T> heap;
    private readonly Comparison<T> compare;
    private int size;
    public PriorityQueue() : this(Comparer<T>.Default) {} 
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
    public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
    public PriorityQueue(int capacity, Comparison<T> comparison)
    {
        this.heap = new List<T>(capacity);
        this.compare = comparison;
    }
    public void Enqueue(T item)
    {
        this.heap.Add(item);
        var i = size++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (compare(this.heap[p], item) <= 0)
                break;
            this.heap[i] = heap[p];
            i = p;
        }
        this.heap[i] = item;

    }
    public T Dequeue()
    {
        var ret = this.heap[0];
        var x = this.heap[--size];
        var i = 0;
        while ((i << 1) + 1 < size)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < size && compare(heap[b], heap[a]) < 0) a = b;
            if (compare(heap[a], x) >= 0)
                break;
            heap[i] = heap[a];
            i = a;
        }
        heap[i] = x;
        heap.RemoveAt(size);
        return ret;
    }
    public T Peek() { return heap[0]; }
    public int Count { get { return size; } }
    public bool Any() { return size > 0; }
}






public struct VT<T, U>
{
	public T Item1; public U Item2;
    public VT(T a, U b) { Item1 = a; Item2 = b; }
}
public struct VT<T, U, V>
{
	public T Item1; public U Item2; public V Item3;
    public VT(T a, U b, V c) { Item1 = a; Item2 = b; Item3 = c; }
}
public struct VT<T, U, V, W>
{
	public T Item1; public U Item2; public V Item3; public W Item4;
    public VT(T a, U b, V c, W d) { Item1 = a; Item2 = b; Item3 = c; Item4 = d; }
}

public class Printer : System.IO.StreamWriter
{
	public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } }
	public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
	public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
}
public static class MyIO
{
	private static char[] splitter = new char[] {' '};
	private static bool eq<T, U>() => typeof(T).Equals(typeof(U));
	private static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
	private static T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
	                                  : eq<T, long>()   ? ct<T, long>(long.Parse(s))
	                                  : eq<T, double>() ? ct<T, double>(double.Parse(s, System.Globalization.CultureInfo.InvariantCulture))
	                                  : eq<T, char>()   ? ct<T, char>(s[0])
	                                                    : ct<T, string>(s);				
	public static string[] ReadMulti<T>(out T a) {
		var ar = Console.ReadLine().Split(splitter, StringSplitOptions.RemoveEmptyEntries); 
		a = cv<T>(ar[0]);
		return ar;
	}
	public static string[] ReadMulti<T, U>(out T a, out U b) {
		var ar = ReadMulti<T>(out a); 
        b = cv<U>(ar[1]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V>(out T a, out U b, out V c) {
		var ar = ReadMulti<T, U>(out a, out b); 
        c = cv<V>(ar[2]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W>(out T a, out U b, out V c, out W d) {
		var ar = ReadMulti<T, U, V>(out a, out b, out c); 
        d = cv<W>(ar[3]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e) {
		var ar = ReadMulti<T, U, V, W>(out a, out b, out c, out d); 
        e = cv<X>(ar[4]);
		return ar;
	}
	public static string[] ReadMulti<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f) {
		var ar = ReadMulti<T, U, V, W, X>(out a, out b, out c, out d, out e); 
        f = cv<Y>(ar[5]);
		return ar;
	}
	public static string[] ReadArray<T>(out T[] a) {		
		var ar = Console.ReadLine().Split(splitter, StringSplitOptions.RemoveEmptyEntries);
		a = ar.Select(cv<T>).ToArray();
		return ar;
	}		
	public static string[][] ReadLines<T>(int n, out T[] a) {
		a = new T[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) arr[i] = ReadMulti(out a[i]);
		return arr;
	}
	public static string[][] ReadLines<T, U>(int n, out VT<T, U>[] a) {
		a = new VT<T, U>[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) {
			T o; U p;
			arr[i] = ReadMulti(out o, out p);
			a[i] = new VT<T, U>(o, p);
		}
		return arr;
	}
	public static string[][] ReadLines<T, U, V>(int n, out VT<T, U, V>[] a) {
		a = new VT<T, U, V>[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) {
			T o; U p; V q;
			arr[i] = ReadMulti(out o, out p, out q);
			a[i] = new VT<T, U, V>(o, p, q);
		}
		return arr;
	}
	public static string[][] ReadLines<T, U, V, W>(int n, out VT<T, U, V, W>[] a) {
		a = new VT<T, U, V, W>[n];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) {
			T o; U p; V q; W r;
			arr[i] = ReadMulti(out o, out p, out q, out r);
			a[i] = new VT<T, U, V, W>(o, p, q, r);
		}
		return arr;
	}
	public static string[][] ReadMatrix<T>(int n, out T[][] a) {
		a = new T[n][];
		string[][] arr = new string[n][];
		for(int i=0; i<n; i++) arr[i] = ReadArray(out a[i]);
		return arr;
	}

	private static void wwp(Action act){
		var sw = new Printer(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);
		act();
		Console.Out.Flush();
		sw.AutoFlush = true;
		Console.SetOut(sw);
	}
	private static string wfm(Type t){
		return t.Equals(typeof(double)) ? "{0:F10}" : "{0}";
	}
	public static void WriteMulti(params object[] a) {
		wwp(()=>{
			for(int i=0;i<a.Length;i++) {
				string fs = wfm(a[i].GetType()) + ((i<a.Length-1) ? " " : Environment.NewLine);
				Console.Write(fs, a[i]);
			}
		});
	}
	public static void WriteArray<T>(T[] a) {
		wwp(()=>{
			string fs = wfm(typeof(T));
			string fs1 = fs + " ";
			string fs2 = fs + Environment.NewLine;
			for(int i=0;i<a.Length;i++) Console.Write( ((i<a.Length-1) ? fs1 : fs2), a[i]);
		});
	}
	public static void WriteLines<T>(T[] a) {
		wwp(()=>{
			string fs = wfm(typeof(T)) + Environment.NewLine;
			foreach(T x in a) Console.Write(fs, x);
		});
	}



}





Measured memory_bytes: 36128