program main
implicit None
	integer(8)::n,k,i,p,s,u,f,q
	integer(8),allocatable::t(:),d(:),c(:)
	
	read*,n,k
	allocate(t(n),d(n),c(n))
	
	do i = 1,n
		read*,t(i),d(i)
	enddo
	
	call h2(d,t,n)
	d(1:n) = d(n:1:-1)
	t(1:n) = t(n:1:-1)
	p =0
	c =0
	do i = 1,k
		p = p + d(i)
		c(t(i)) = c(t(i)) + 1
	enddo
	
	s = 0
	do i = 1,n
		if(c(i) > 0) s = s+1
	enddo
	q = p +s*s
	
	u = k
	f = k+1
	
	do i = f,n
		if(c(t(i)) /= 0)cycle
		do
			if(u == 0)exit
			if(c(t(u)) == 1)then
				u = u-1
				else
				exit
			endif
		enddo
		if(u == 0)exit
			c(t(u)) = c(t(u))-1
			p = p-d(u)+d(i)
			s = s+1
			u = u-1
		if(q < p+s*s) q = p+s*s
	enddo
	
	print "(i0)",q
end program main

subroutine h2(a,b,n)
implicit None
	integer(8)::a(n),b(n),x,y
	integer(8)::n,i,ie,i0,i1,i2
	
	do i = n/2,1,-1
		x = a(i);y = b(i);ie = n + 1; i0 = i; i1 = i0 * 2
		do while(i1 < ie)
			i2 = i1 + 1
			if(i2 < ie .and. a(i1) < a(i2)) i1 = i2
			if(a(i1) > x)then
				a(i0) = a(i1);a(i1) = x
				b(i0) = b(i1);b(i1) = y
				else
				exit
			endif
			i0 = i1;i1 = i0 *2
		enddo
	enddo
	do ie = n,2,-1
		x = a(ie);y = b(ie)
		a(ie) = a(1);b(ie) = b(1)
		a(1) = x;b(1) = y
		i0 =1;i1 =2
		do while(i1 <ie)
			i2 = i1 +1
			if(i2 < ie .and. a(i1) < a(i2)) i1 = i2
			if(a(i1) > x)then
				a(i0) = a(i1);a(i1) = x
				b(i0) = b(i1);b(i1) = y
				else
				exit
			endif
			i0 = i1;i1 = i0 *2
		enddo
	enddo
end subroutine h2