program test
implicit none
integer(8) :: i=0,j=0,n=0,k=0,t(100000)=0,d(100000)=0,dummy(100000)=0,num=0
integer(8) :: tt(100000)=0,dd(100000)=0,lost(100000)=0,lost_cum(100000)=0
integer(8) :: get(100000)=0,get_cum(100000)=0,total(100000)=0,sumi_a(100000)=0,sumi_b(100000)=0
integer(8) :: kind_max_a(100000)=0,kind_max_b(100000)=0,kind_count=0,lost_count=0,get_count=0,count=0,error

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

if(n==k) then
	goto 100
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個だけ残して、それ以外は新たな種類の寿司に置換される可能性がある
	lost_count = 0
	do i=1,k
		if(dd(i) == kind_max_a(tt(i)) .and. sumi_a(tt(i)) == 0 ) then
			sumi_a(tt(i)) = 1
		else
			lost_count=lost_count+1
			lost(lost_count) = dd(i)
		endif
	enddo
	
	if(lost_count == 0)then
		goto 200
	endif
	
	!昇順ソートをかける
	call heapsort_up(lost_count,lost(1:lost_count),dummy(1:lost_count))
	
	!失う価値の累積和
	do i=1,lost_count
		if(i == 1) then
			lost_cum(i) = lost(1)
		else
			lost_cum(i) = lost_cum(i-1) + lost(i)
		endif
	enddo
	
	!食べるグループの種類は何種類？
	call heapsort_up(k,tt(1:k),dd(1:k))
	kind_count = 1
	if(k>=2)then
		do i =2,k
			if(tt(i) .ne. tt(i-1))then
			 kind_count = kind_count + 1
			endif
		enddo
	endif
	
	!食べないグループで、各種類の最高値を列挙
	do i=k+1,n
		kind_max_b(tt(i)) = max(kind_max_b(tt(i)),dd(i))
	enddo
	
	!食べないグループで、各種類の最高値にあたり、かつ食べるグループにない寿司が置換に使われる可能性がある
	get_count = 0
	do i=k+1,n
		if((dd(i) == kind_max_b(tt(i))) .and. kind_max_a(tt(i)) == 0 .and. sumi_b(tt(i)) == 0) then
			get_count = get_count + 1
			get(get_count) = dd(i)
			sumi_b(tt(i)) = 1
		endif
	enddo
	
	if(get_count == 0)then
		goto 300
	endif
	
	!降順ソートをかける
	call heapsort_down(get_count,get(1:get_count),dummy(1:get_count))
	
	!得る価値
	do i=1,get_count
		if(i == 1) then
			get_cum(i) = get(1) + 2*(kind_count+i)-1
		else
			get_cum(i) = get_cum(i-1) + get(i) +  2*(kind_count+i)-1
		endif
	enddo
	
	count = min(lost_count,get_count)
	
	do i = 1,count
		total(i) = get_cum(i) - lost_cum(i)
	enddo
	
	write(*,*) sum(d(1:k))+ kind_count*kind_count+ max(0,maxval(total(1:count)))
endif

!n=kのとき
if(1 == 0)then
100 continue
	call heapsort_up(k,t(1:k),d(1:k))
	num = 1
	if(k>=2)then
		do i =2,k
			if(t(i) .ne. t(i-1))then
			 num = num + 1
			endif
		enddo
	endif
	write(*,*) sum(d(1:k)) + num*num
endif

!lost_count=0、つまり美味しい寿司から貪欲に探査した場合1種類ずつの寿司になっているとき
if(1 == 0)then
200 continue
	call heapsort_up(k,tt(1:k),dd(1:k))
	num = 1
	if(k>=2)then
		do i =2,k
			if(tt(i) .ne. tt(i-1))then
			 num = num + 1
			endif
		enddo
	endif
	call heapsort_down(k,dd(1:k),tt(1:k))
	write(*,*) sum(dd(1:k)) + num*num
endif

!get_count=0、つまり最初は食べるつもりのなかった寿司が、全て最初食べるつもりだった寿司と同じ種類だった場合
if(1 == 0)then
300 continue
	call heapsort_up(k,tt(1:k),dd(1:k))
	num = 1
	if(k>=2)then
		do i =2,k
			if(tt(i) .ne. tt(i-1))then
			 num = num + 1
			endif
		enddo
	endif
	call heapsort_down(k,dd(1:k),tt(1:k))
	write(*,*) sum(dd(1:k)) + num*num
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

Measured memory_bytes: 9984