#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"from heapq import*\n"
"I=lambda:list(map(int,input().split()))[::-1]\n"
"k,n=I()\n"
"q=[]\n"
"v=i=T=A=0\n"
"l=[0]*-~n\n"
"for b,a in sorted(I()for _ in[0]*n)[::-1]:\n"
" if i<k:\n"
"  if l[a]:heappush(q,b)\n"
"  else:T+=v*2+1;v+=1\n"
"  T+=b\n"
" elif l[a]^1and q:T+=b+v*2+1-heappop(q);v+=1\n"
" A=max(A,T);i+=1;l[a]=1\n"
"print(A)\n"
"\"";
  system(s);
  return 0;
}            