program test
implicit none
integer(8) :: i,j,n,k,t(10000),d(10000),dummy(10000)=0,num
integer(8) :: tt(10000),dd(10000),lost(10000)=0,get(10000)=0,total(10000)=0,sumi(10000)=0
integer(8) :: kind_max_a(10000)=0,kind_max_b(10000)=0,kind_count_a=0,kind_count_b=0

read(*,*) n,k
do i=1,n
	read(*,*) t(i),d(i)
enddo

if(n==k) then
	call heapsort_up(n,t(1:n),d(1:n))
	num = 1
	do i =2,n
		if(t(i) .ne. t(i-1))then
		 num = num + 1
		endif
	enddo
	write(*,*) sum(d(1:n)) + num*num
else
	!まずは降順に並べる
	call heapsort_down(n,d(1:n),t(1:n))
	
	!1～k番目が暫定食べる、k+1～n番目が食べない
	tt(1:n) = t(1:n)
	dd(1:n) = d(1:n)
	
	!食べるグループで、各種類の最高値を計算
	do i=1,k
		kind_max_a(tt(i)) = max(kind_max_a(tt(i)),dd(i))
	enddo
	
	!食べるグループで、各種類の最高値を1度だけ潰す
	do i=1,k
		if(dd(i) == kind_max_a(tt(i)) .and. sumi(tt(i)) == 0 ) then
			dd(i) = 10**10
			sumi(tt(i)) = 1
		endif
	enddo
	
	!昇順ソートをかける
	call heapsort_up(k,dd(1:k),dummy(1:k))
	
	!失う価値
	do i=1,k
		if(i == 1) then
			lost(i) = dd(1)
		else
			lost(i) = lost(i-1) + dd(i)
		endif
	enddo
	
	kind_count_a=1
	!食べるグループの種類を数える
	call heapsort_up(k,tt(1:k),dummy(1:k))
	if(i == 1)then
		kind_count_a = 1
	else
	do i=2,k
		if(tt(i) .ne. tt(i-1))then
			kind_count_a = kind_count_a+1
		endif
	enddo
	endif
	
	!食べないグループで、各種類の最高値を列挙
	do i=k+1,n
		kind_max_b(tt(i)) = max(kind_max_b(tt(i)),dd(i))
	enddo
	
	!食べないグループで、各種類の最高以外または食べるグループにあるやつを潰す
	do i=k+1,n
		if((dd(i) .ne. kind_max_b(tt(i))) .or. kind_max_a(tt(i))>0 ) then
			dd(i) = 0
		endif
	enddo
	
	!降順ソートをかける
	call heapsort_down(k,dd(k+1:n),dummy(k+1:n))
	
	!得る価値
	do i=k+1,n
		if(i == k+1) then
			get(i-k) = dd(k+1) + 2 * (kind_count_a+1) -1
		else
			get(i-k) = get(i-k-1) + dd(i) + 2 * (kind_count_a+i-k) -1
		endif
	enddo

	do i = 1,min(k,n-k)
		total(i) = get(i) - lost(i)
	enddo
	
	write(*,*) sum(d(1:k))+ kind_count_a*kind_count_a + max(0,maxval(total(1:min(k,n-k))))
	
endif

contains
 
subroutine heapsort_down(n,y1,y2)
 
	implicit none
	integer(8),intent(in) :: n
	integer(8),intent(inout) :: y1(1:n)
	integer(8),intent(inout) :: y2(1:n)
	integer(8) :: i,k,j,l
	integer(8) :: t1,t2
	
	l = n/2+1
	k = n
 
	do while (k /= 1)
		 if(l > 1) then
				l = l-1
				t1 = y1(l)
				t2 = y2(l)
				
		 else
				t1 = y1(k)
				t2 = y2(k)
				y1(k) = y1(1)
				y2(k) = y2(1)
				k = k-1
				if(k == 1) then
					 y1(1) = t1
					 y2(1) = t2
					 exit
				endif
		 endif
 
		 i = l
		 j = l+l
 
		 do while(j <= k)
				if(j < k) then
					 if(y1(j) > y1(j+1)) j = j+1
				endif
				
				if (t1 > y1(j)) then
					 y1(i) = y1(j)
					 y2(i) = y2(j)
					 i = j
					 j = j+j
				else
					 j = k+1
				endif
		 
		 enddo
		 
		 y1(i) = t1
		 y2(i) = t2
	
	enddo
	return
 
end subroutine heapsort_down

subroutine heapsort_up(n,y1,y2)
 
	implicit none
	integer(8),intent(in) :: n
	integer(8),intent(inout) :: y1(1:n)
	integer(8),intent(inout) :: y2(1:n)
	integer(8) :: i,k,j,l
	integer(8) :: t1,t2
	
	l = n/2+1
	k = n
 
	do while (k /= 1)
		 if(l > 1) then
				l = l-1
				t1 = y1(l)
				t2 = y2(l)
				
		 else
				t1 = y1(k)
				t2 = y2(k)
				y1(k) = y1(1)
				y2(k) = y2(1)
				k = k-1
				if(k == 1) then
					 y1(1) = t1
					 y2(1) = t2
					 exit
				endif
		 endif
 
		 i = l
		 j = l+l
 
		 do while(j <= k)
				if(j < k) then
					 if(y1(j) < y1(j+1)) j = j+1
				endif
				
				if (t1 < y1(j)) then
					 y1(i) = y1(j)
					 y2(i) = y2(j)
					 i = j
					 j = j+j
				else
					 j = k+1
				endif
		 
		 enddo
		 
		 y1(i) = t1
		 y2(i) = t2
	
	enddo
	return
 
end subroutine heapsort_up

end program