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


public class Pair
{
	public long T { get; private set; }
	public long D { get; private set; }

	public Pair(long t, long d)
	{
		T = t;
		D = d;
	}
}


public class D
{
	public static void Main()
	{
		int N = GetInt();
		int K = GetInt();
		List<Pair> pairs = new List<Pair>(N);
		for(int i = 0; i < N; i++)
			pairs.Add(new Pair(GetLong(), GetLong()));
		pairs.Sort((p,q) => (int)(q.D - p.D));

		bool[] usedNeta = new bool[N+1];
		PriorityQueue<long> nextRemove = new PriorityQueue<long>(N, 0);
		PriorityQueue<long> nextAdd = new PriorityQueue<long>(N, 1);
		
		long basePoint = 0;
		int x = 0;
		for(int i = 0; i < K; i++)
		{
			Pair pair = pairs[i];
			basePoint += pair.D;

			if(usedNeta[pair.T])
			{
				nextRemove.Push(pair.D);								
			}
			else
			{
				usedNeta[pair.T] = true;
				x++;
			}			
		}

		for(int i = K; i < N; i++)
		{
			Pair pair = pairs[i];
			if(usedNeta[pair.T])
				continue;

			usedNeta[pair.T] = true;
			nextAdd.Push(pair.D);
		}

		long[] f = new long[N+1];
		for(int i = 1; i <= N; i++)
			f[i] = long.MinValue;
		f[x] = basePoint;
		for(int a = x + 1; a <= N; a++)
		{
			if(nextRemove.Size == 0)
				break;
			if(nextAdd.Size == 0)
				break;

			basePoint -= nextRemove.Pop();
			basePoint += nextAdd.Pop();
			f[a] = basePoint;
		}

		long[] g = new long[N+1];
		long ans = long.MinValue;
		for(long i = x; i <= N; i++)
		{
			g[(int)i] = f[(int)i] + i * i;
			ans = Math.Max(ans, g[(int)i]);
		}
		Console.WriteLine(ans);		
	}
}



public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


public class PriorityQueue<T> where T:IComparable<T>
{
	public long Size { get; private set; } = 0;
	public long MaxSize { get; private set; } = 0;
	private T[] m_heap;
	public int Type { get; private set; } = 0;  // 0: ascending
	
	public PriorityQueue(long maxSize, int type)
	{
		if(maxSize <= 0)
			throw new Exception();
		MaxSize = maxSize;
		m_heap = new T[maxSize];
		
		Type = type;
	}
	
	private int Compare(T x, T y)
	{
		return (Type == 0) ? x.CompareTo(y) : y.CompareTo(x);
	}
	
	public void Push(T x)
	{
		if(Size == MaxSize)
			throw new Exception("Queue is full.");
		
		long i = Size++;
		while(i > 0)
		{
			long p = (i - 1)/2;
			if(Compare(m_heap[p],x) <= 0)
				break;
			m_heap[i] = m_heap[p];
			i = p;			
		}
		m_heap[i] = x;		
	}
	
	public T Pop()
	{
		if(Size == 0)
			throw new Exception("Queue is empty.");
		
		T result = m_heap[0];
		T x = m_heap[--Size];
		long i = 0;
		while(i * 2 + 1 < Size)
		{
			long c1 = i * 2 + 1, c2 = i * 2 + 2;
			if(c2 < Size && Compare(m_heap[c2], m_heap[c1]) < 0)
				c1 = c2;
			if(Compare(m_heap[c1], x) >= 0)
				break;
			m_heap[i] = m_heap[c1];
			i = c1;
		}
		m_heap[i] = x;
		
		return result;		
	}	
}


Measured memory_bytes: 26176