You have a playlist consisting of $n$ songs. The $i$-th song is characterized by two numbers $t_i$ and $b_i$ — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $3$ songs having lengths $[5, 7, 4]$ and beauty values $[11, 14, 6]$ is equal to $(5 + 7 + 4) \cdot 6 = 96$.

You need to choose at most $k$ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.

Each of the next $n$ lines contains two integers $t_i$ and $b_i$ ($1 \le t_i, b_i \le 10^6$) — the length and beauty of $i$-th song.


-----Output-----

Print one integer — the maximum pleasure you can get.


-----Examples-----
Input
4 3
4 7
15 1
3 6
6 8

Output
78

Input
5 3
12 31
112 4
100 100
13 55
55 50

Output
10000



-----Note-----

In the first test case we can choose songs ${1, 3, 4}$, so the total pleasure is $(4 + 3 + 6) \cdot 6 = 78$.

In the second test case we can choose song $3$. The total pleasure will be equal to $100 \cdot 100 = 10000$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Complete search


Solutions:
import heapq
from sys import stdin
input = stdin.readline
(n, k) = map(int, input().split())
b_t = []
for _ in range(n):
	(t, b) = tuple(map(int, input().split()))
	b_t.append((b, t))
b_t.sort(reverse=True)
ans = 0
time = 0
l = []
for (b, t) in b_t:
	time += t
	heapq.heappush(l, t)
	if len(l) > k:
		c = heapq.heappop(l)
		time -= c
	ans = max(ans, time * b)
print(ans)


from collections import defaultdict as dd
import math
import heapq

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
(n, k) = mi()
songs = []
for i in range(n):
	songs.append(lm())
songs.sort(key=lambda x: -x[1])
h = []
maxsofar = 0
newlen = 0
for i in range(n):
	beauty = songs[i][1]
	heapq.heappush(h, songs[i][0])
	removed = 0
	if i >= k:
		removed = heapq.heappop(h)
	newlen = newlen + songs[i][0] - removed
	maxsofar = max(maxsofar, newlen * beauty)
print(maxsofar)


from __future__ import print_function
from sys import stdin
from collections import *
from operator import itemgetter
from heapq import *
import os, sys, atexit

def arr_inp(n):
	if n == 1:
		return [int(x) for x in input().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])
(n, k) = arr_inp(1)
(cur, ans, queue, arr) = (0, 0, [], [])
heapify(queue)
for i in range(n):
	(x, y) = arr_inp(1)
	arr.append([x, y])
arr.sort(key=lambda x: x[1], reverse=True)
for i in range(n):
	heappush(queue, arr[i][0])
	cur += arr[i][0]
	if i >= k:
		cur -= heappop(queue)
	ans = max(ans, cur * arr[i][1])
print(ans)


import sys
input = sys.stdin.readline
from heapq import heappush, heappop
(n, k) = map(int, input().split())
arr = []
for i in range(n):
	(t, b) = map(int, input().split())
	arr.append((b, t))
arr.sort(reverse=True)
ans = 0
Sum = 0
heap = []
for (b, t) in arr:
	Sum += t
	heappush(heap, t)
	if len(heap) > k:
		Sum -= heappop(heap)
	ans = max(ans, Sum * b)
print(ans)


from copy import deepcopy

class PriorityQueue:

	def __init__(self):
		self.elements = [(0, None)]
		self.size = 0
		self.capacity = 1000

	def push(self, item):
		self.size += 1
		self.elements.append(item)
		i = self.size
		while self.elements[i // 2][0] > item[0]:
			self.elements[i] = self.elements[i // 2]
			i = i // 2
		self.elements[i] = item

	def poll(self):
		if self.size <= 0:
			return None
		min_element = deepcopy(self.elements[1])
		last_element = self.elements.pop()
		self.size -= 1
		i = 1
		while i * 2 <= self.size:
			child = i * 2
			if child != self.size and self.elements[child + 1][0] < self.elements[child][0]:
				child += 1
			if last_element[0] > self.elements[child][0]:
				self.elements[i] = self.elements[child]
			else:
				break
			i = child
		if self.size > 0:
			self.elements[i] = last_element
		return min_element
import heapq
(n, k) = tuple(map(int, input().split(' ')))
s = []
for i in range(n):
	t = tuple(map(int, input().split(' ')))
	s.append(t)

def get_beauty(e):
	return e[1]
s.sort(reverse=True, key=get_beauty)
max_score = 0
sum_len = 0
heap = []
try:
	for i in range(n):
		length = s[i][0]
		beauty = s[i][1]
		sum_len += length
		if i + 1 > k:
			sum_len -= heapq.heappop(heap)
		heapq.heappush(heap, length)
		score = sum_len * beauty
		max_score = max(max_score, score)
except Exception as e:
	print(e)
print(max_score)


import heapq

def argsort(seq):
	return sorted(range(len(seq)), key=seq.__getitem__)
(n, k) = map(int, input().split())
a = []
b = []
c = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
	c.append([x, y])
ind = argsort(b)
b = sorted(b)
b = b[::-1]
ind = ind[::-1]
na = []
for i in range(n):
	na.append(a[ind[i]])
a = na
ta = [a[0]]
sm = sum(ta)
mnd = b[0]
count = 1
p = 0
res = sm * mnd
queue = [a[0]]
for i in range(1, n):
	if count >= k:
		heapq.heappush(queue, a[i])
		sm = sm - heapq.heappop(queue) + a[i]
		mnd = b[i]
		res = max(res, sm * mnd)
	else:
		sm = sm + a[i]
		mnd = b[i]
		heapq.heappush(queue, a[i])
		count += 1
		res = max(res, sm * mnd)
print(res)


from heapq import *
(n, k) = map(int, input().split())
a = []
for i in range(n):
	(y, x) = map(int, input().split())
	a.append([x, y])
a.sort(reverse=True)
ans = 0
s = 0
hp = []
for i in range(n):
	s += a[i][1]
	heappush(hp, a[i][1])
	if i >= k:
		s -= heappop(hp)
	ans = max(ans, a[i][0] * s)
print(ans)


from heapq import heappush, heappop
heapObj = []
(n, k) = map(int, input().strip().split())
l = []
for i in range(n):
	(t, b) = map(int, input().strip().split())
	l.append([b, t])
l.sort()
ct = 0
ans = 0
sm = 0
for i in range(n - 1, -1, -1):
	if ct < k:
		ct += 1
		sm += l[i][1]
		heappush(heapObj, l[i][1])
	else:
		mn = heapObj[0]
		if l[i][1] > mn:
			heappop(heapObj)
			heappush(heapObj, l[i][1])
			sm = sm - mn + l[i][1]
	ans = max(ans, l[i][0] * sm)
print(ans)


import heapq
(n, k) = map(int, input().split())
a = []
for _ in range(n):
	(t, b) = map(int, input().split())
	a.append((b, t))
a.sort(reverse=True)
q = []
ans = 0
s = 0
for i in a:
	s += i[1]
	heapq.heappush(q, i[1])
	if len(q) > k:
		s -= heapq.heappop(q)
	ans = max(ans, s * i[0])
print(ans)


import heapq as h
plist = []
h.heapify(plist)
(n, k) = map(int, input().split())
q = []
for _ in range(n):
	(t, d) = map(int, input().split())
	q.append([d, t])
q.sort(reverse=True)
sm = 0
ans = 0
for i in range(n):
	h.heappush(plist, q[i][1])
	sm += q[i][1]
	if i >= k:
		y = h.heappop(plist)
		sm -= y
	ans = max(ans, sm * q[i][0])
print(ans)


import heapq
(n, k) = map(int, input().split())
music = []
for i in range(n):
	(length, beauty) = map(int, input().split())
	music.append((beauty, length))
music.sort(reverse=True)
s = []
ma = 0
sumlength = 0
for i in range(n):
	if len(s) == k:
		t = heapq.heappushpop(s, music[i][1])
	else:
		heapq.heappush(s, music[i][1])
		t = 0
	sumlength += music[i][1] - t
	ma = max(sumlength * music[i][0], ma)
print(ma)


from heapq import *
(n, k) = list(map(int, input().split()))
a = []
for i in range(n):
	(t, b) = list(map(int, input().split()))
	a.append([b, t])
a.sort(reverse=True)
ans = 0
l = 0
h = []
for (b, t) in a:
	l += t
	heappush(h, t)
	if len(h) > k:
		l -= heappop(h)
	ans = max(ans, l * b)
print(ans)


import sys
from heapq import heappush, heappop

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(self.next())

	def cal(self, s):
		if len(s) == 1:
			return s[0]
		if s[0] == 0:
			return self.cal(s[1:])
		v = 1
		for c in s:
			v *= c
		return v

	def solve(self):
		n = self.next_int()
		k = self.next_int()
		rs = sorted([(self.next_int(), self.next_int()) for _ in range(0, n)], key=lambda x: x[1], reverse=True)
		heap = []
		sum = 0
		ans = 0
		for (x, b) in rs:
			heappush(heap, x)
			sum += x
			if len(heap) > k:
				sum -= heappop(heap)
			ans = max(ans, sum * b)
		print(ans)
Main().solve()


import heapq
(N, K) = map(int, input().split())
items = []
for i in range(N):
	items.append(tuple(map(int, input().split())))
b_index = sorted([(i, items[i][1]) for i in range(N)], key=lambda x: -x[1])
ans = -1
sum_num = 0
que = []
heapq.heapify(que)
for (i, b) in b_index:
	t = items[i][0]
	if len(que) < K:
		heapq.heappush(que, t)
		sum_num += t
	else:
		rem = heapq.heappop(que)
		if rem < t:
			heapq.heappush(que, t)
			sum_num -= rem
			sum_num += t
		else:
			heapq.heappush(que, rem)
	ans = max(ans, b * sum_num)
print(ans)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, k) = ria()
		z = []
		for i in range(n):
			z.append(ria())
		z.sort(key=lambda x: x[1], reverse=True)
		q = []
		ans = 0
		curr = 0
		for i in range(n):
			curr += z[i][0]
			heappush(q, z[i][0])
			if len(q) == k + 1:
				curr -= heappop(q)
			ans = max(ans, curr * z[i][1])
		print(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from sys import stdin
import heapq
input = stdin.readline

def f(a, k):
	h = []
	ans = -222222222
	a = sorted(a, key=lambda s: s[1], reverse=True)
	s = 0
	for (ad, p) in a:
		heapq.heappush(h, ad)
		s += ad
		if len(h) > k:
			s -= heapq.heappop(h)
		ans = max(ans, s * p)
	return ans
(n, m) = map(int, input().strip().split())
blanck = []
for i in range(n):
	(x, y) = map(int, input().strip().split())
	blanck.append((x, y))
print(f(blanck, m))


import heapq
import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
(n, k) = mi()
s = []
for _ in range(n):
	(i, j) = mi()
	s.append((j, i))
s = sorted(s)[::-1]
d = []
sm = 0
smm = 0
for (i, (s_b, s_len)) in enumerate(s):
	if i < k:
		sm += s_len
		heapq.heappush(d, s_len)
	else:
		sm += s_len - d[0]
		heapq.heappop(d)
		heapq.heappush(d, s_len)
	smm = max(smm, s_b * sm)
print(smm)


import sys
import heapq

def input():
	return sys.stdin.readline()
(n, k) = map(int, input().split())
arr = [(0, 0)] * n
for i in range(n):
	(t, b) = map(int, input().split())
	arr[i] = (t, b)
arr.sort(key=lambda x: (-x[1], -x[0]))
sum_length = 0
heap_length = []
for i in range(k):
	sum_length += arr[i][0]
	heapq.heappush(heap_length, arr[i][0])
min_beauty = arr[k - 1][1]
answer = sum_length * min_beauty
for i in range(k, n):
	min_beauty = arr[i][1]
	min_length = heapq.heappop(heap_length)
	temp = arr[i][0] - min_length
	if temp > 0:
		sum_length += temp
		heapq.heappush(heap_length, arr[i][0])
	else:
		heapq.heappush(heap_length, min_length)
	answer = max(answer, sum_length * min_beauty)
sum_length = 0
for i in range(k):
	sum_length += arr[i][0]
	min_beauty = arr[i][1]
	answer = max(answer, sum_length * min_beauty)
print(answer)


import math
from decimal import Decimal
import heapq

def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return (n, b)

def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return (n, b, c)

def dv():
	(n, m) = map(int, input().split())
	return (n, m)

def dva():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return (n, m, b)

def eratosthenes(n):
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))

def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return (n, b, m, c)

def dvs():
	n = int(input())
	m = int(input())
	return (n, m)
(n, k) = map(int, input().split())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append((y, x))
a.sort(reverse=True)
(ans, mx, b) = (0, 0, [])
for (x, y) in a:
	mx += y
	heapq.heappush(b, y)
	if len(b) > k:
		mx -= heapq.heappop(b)
	ans = max(ans, mx * x)
print(ans)


import heapq
(n, k) = map(int, str(input()).split(' '))
tab = []
for i in range(n):
	(ti, bi) = map(int, str(input()).split(' '))
	tab.append((bi, ti))
tab.sort(key=lambda e: -e[0])
temps = 0
maxi = -float('inf')
h = []
for ii in range(n):
	(bb, tt) = tab[ii]
	if len(h) < k:
		temps += tt
		heapq.heappush(h, tt)
	else:
		tta = heapq.heappushpop(h, tt)
		temps += tt - tta
	maxi = max(maxi, bb * temps)
print(maxi)


from heapq import heappush, heappop
(N, K) = [int(s) for s in input().split()]
songs = []
for _ in range(N):
	(t, b) = [int(s) for s in input().split()]
	songs.append((t, b))
songs.sort(key=lambda x: x[1], reverse=True)
max_pleasure = 0
total_length = 0
max_lengths = []
for i in range(K):
	total_length += songs[i][0]
	heappush(max_lengths, songs[i][0])
	max_pleasure = max(max_pleasure, total_length * songs[i][1])
for i in range(K, N):
	if max_lengths[0] < songs[i][0]:
		min_length = heappop(max_lengths)
		heappush(max_lengths, songs[i][0])
		total_length = total_length - min_length + songs[i][0]
		max_pleasure = max(max_pleasure, total_length * songs[i][1])
print(max_pleasure)


import sys
mod = 10 ** 9 + 7
from sys import stdin, stdout

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def ain():
	return list(map(int, sin().split()))

def sin():
	return stdin.readline()

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def merge1(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [0] * n1
	R = [0] * n2
	for i in range(0, n1):
		L[i] = arr[l + i]
	for j in range(0, n2):
		R[j] = arr[m + 1 + j]
	(i, j, k) = (0, 0, l)
	while i < n1 and j < n2:
		if L[i][1] < R[j][1]:
			arr[k] = L[i]
			i += 1
		elif L[i][1] > R[j][1]:
			arr[k] = R[j]
			j += 1
		elif L[i][0] < R[j][0]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergesort1(arr, l, r):
	if l < r:
		m = (l + (r - 1)) // 2
		mergesort1(arr, l, m)
		mergesort1(arr, m + 1, r)
		merge1(arr, l, m, r)

def merge2(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [0] * n1
	R = [0] * n2
	for i in range(0, n1):
		L[i] = arr[l + i]
	for j in range(0, n2):
		R[j] = arr[m + 1 + j]
	(i, j, k) = (0, 0, l)
	while i < n1 and j < n2:
		if L[i][0] > R[j][0]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergesort2(arr, l, r):
	if l < r:
		m = (l + (r - 1)) // 2
		mergesort2(arr, l, m)
		mergesort2(arr, m + 1, r)
		merge2(arr, l, m, r)
(n, k) = ain()
b = []
for i in range(n):
	b.append(ain())
mergesort1(b, 0, n - 1)
r = []
for i in range(n):
	r.append([b[i][0], i])
mergesort2(r, 0, n - 1)
g = [0] * n
s = 0
for i in range(k):
	s += r[i][0]
	g[r[i][1]] = 1
p = k
s1 = 0
for i in range(n):
	q = s * b[i][1]
	s1 = max(s1, q)
	if g[i] == 1:
		s -= b[i][0]
		while p < n:
			if r[p][1] > i:
				s += r[p][0]
				g[r[p][1]] = 1
				p += 1
				break
			p += 1
print(s1)


import sys
input = sys.stdin.readline
import heapq
(N, K) = map(int, input().split())
X = [[0, 0] for _ in range(N)]
for i in range(N):
	(t, b) = map(int, input().split())
	X[i][0] = t
	X[i][1] = b
X = sorted(X, key=lambda x: -x[1])
a = []
s = 0
ma = 0
for i in range(N):
	heapq.heappush(a, X[i][0])
	s += X[i][0]
	if i >= K:
		s -= heapq.heappop(a)
	ma = max(ma, s * X[i][1])
print(ma)


import io, os
from heapq import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, k) = kk()
ls = [None] * n
for i in range(n):
	ls[i] = tuple(kk())
ls.sort(key=lambda x: x[1])
(q, totall, m) = ([], 0, 0)
heapify(q)
for s in reversed(ls):
	if len(q) < k:
		heappush(q, s)
		totall += s[0]
	else:
		m = max(m, s[1] * (totall - q[0][0] + s[0]))
		if s[0] > q[0][0]:
			totall -= heappushpop(q, s)[0]
			totall += s[0]
	m = max(m, totall * s[1])
print(m)


import heapq
(n, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(tuple(map(int, input().split())))
a.sort(key=lambda x: x[1])
b = []
i = n - 1
summ = 0
val = 0
while k > 0:
	summ += a[i][0]
	val = max(val, summ * a[i][1])
	heapq.heappush(b, a[i][0])
	i -= 1
	k -= 1
while i >= 0:
	t = heapq.heappop(b)
	heapq.heappush(b, a[i][0])
	summ -= t
	summ += a[i][0]
	val = max(val, summ * a[i][1])
	i -= 1
print(val)


import heapq
(n, lim) = map(int, input().split())
songs = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: x[1], reverse=True)
h = []
ret = 0
s = 0
for (t, b) in songs:
	s += t
	heapq.heappush(h, t)
	if len(h) > lim:
		s -= heapq.heappop(h)
	ret = max(ret, s * b)
print(ret)


import os, sys, heapq
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil
mod = 10 ** 9 + 7
for _ in range(1):
	(n, k) = map(int, input().split())
	info2 = []
	h = []
	for i in range(n):
		info = list(map(int, input().split()))
		info2.append(info[::-1])
	info2.sort()
	max_pleasure = float('-inf')
	current_sum = 0
	for i in range(n - 1, -1, -1):
		current_sum += info2[i][1]
		heapq.heappush(h, info2[i][1])
		while len(h) > k:
			current_sum -= h[0]
			heapq.heappop(h)
		max_pleasure = max(max_pleasure, current_sum * info2[i][0])
	print(max_pleasure)


from sys import stdin, stdout
import math
import heapq
(n, k) = list(map(int, stdin.readline().split()))
playlist = []
for _ in range(n):
	playlist.append(list(map(int, stdin.readline().split())))
playlist = sorted(playlist, key=lambda x: x[1], reverse=True)
myheap = []
heapq.heapify(myheap)
cur_sum = 0
mx_beauty = -float('inf')
for i in playlist:
	if len(myheap) < k:
		cur_sum += i[0]
		heapq.heappush(myheap, i)
		mx_beauty = max(mx_beauty, cur_sum * i[1])
	else:
		(first, second) = heapq.heappop(myheap)
		if first < i[0]:
			cur_sum -= first
			cur_sum += i[0]
			heapq.heappush(myheap, i)
			mx_beauty = max(mx_beauty, cur_sum * i[1])
		else:
			heapq.heappush(myheap, [first, second])
			continue
print(mx_beauty)


import sys
import io, os
input = sys.stdin.buffer.readline
(n, k) = map(int, input().split())
BT = []
for i in range(n):
	(t, b) = map(int, input().split())
	BT.append((b, t))
BT.sort(reverse=True)
A = []
ans = -10 ** 18
s = 0
for i in range(k):
	(b, t) = BT[i]
	A.append(t)
	s += t
	ans = max(ans, s * b)
import heapq
heapq.heapify(A)
for i in range(k, n):
	(b, t) = BT[i]
	s -= A[0]
	s += t
	heapq.heappop(A)
	heapq.heappush(A, t)
	ans = max(ans, s * b)
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
MOD = 1000000007

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, k) = value()
play = []
for i in range(n):
	(t, b) = value()
	play.append((b, t))
play.sort()
Heap = [inf]
need = k - 1
ans = 0
d = 0
for i in range(n - 1, n - need - 1, -1):
	ans = max(ans, (d + play[i][1]) * play[i][0])
	Heap.append(play[i][1])
	d += play[i][1]
heapify(Heap)
ans = max((play[n - need - 1][1] + d) * play[n - need - 1][0], ans)
for i in range(n - need - 2, -1, -1):
	if play[i + 1][1] > Heap[0]:
		d += play[i + 1][1] - Heap[0]
		heappop(Heap)
		heappush(Heap, play[i + 1][1])
	ans = max(ans, (play[i][1] + d) * play[i][0])
print(ans)


from sys import stdin
import heapq
input = stdin.readline
(n, k) = map(int, input().split())
tb = [list(map(int, input().split())) for i in range(n)]
tb.sort(key=lambda x: x[1])
hq = []
s = 0
ans = 0
for i in range(k):
	heapq.heappush(hq, tb[n - 1 - i][0])
	s += tb[n - 1 - i][0]
	ans = max(ans, s * tb[n - 1 - i][1])
for i in range(n - k)[::-1]:
	val = heapq.heappop(hq)
	y = max(tb[i][0], val)
	s += y - val
	heapq.heappush(hq, y)
	ans = max(ans, s * tb[i][1])
print(ans)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
import heapq
(n, k) = mi()
a = []
for _ in range(n):
	(x, y) = mi()
	a.append((x, y))
a = sorted(a, key=lambda x: x[1])
h = []
heapq.heapify(h)
m = 0
y = 0
c = 0
s = 0
for i in range(n - 1, -1, -1):
	c += 1
	d = a[i][0] + s
	g = a[i][1]
	f = d * g
	m = max(m, f)
	heapq.heappush(h, a[i][0])
	x = 0
	if c >= k:
		x = heapq.heappop(h)
	s = s - x + a[i][0]
print(m)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z
(n, k) = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
a = sort_list(a, b)
a.reverse()
b.sort(reverse=True)
s = []
sum = 0
ans = 0
for i in range(n):
	if i == k:
		heapq.heapify(s)
	if i < k:
		s.append(a[i])
		sum += a[i]
		ans = max(sum * b[i], ans)
	else:
		e = heapq.heappop(s)
		sum -= e
		sum += a[i]
		ans = max(sum * b[i], ans)
		if a[i] > e:
			heapq.heappush(s, a[i])
		else:
			heapq.heappush(s, e)
			sum += e - a[i]
print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq

def main():
	(n, k) = map(int, input().split())
	a = list((list(map(int, input().split()))[::-1] for _ in range(n)))
	a.sort(reverse=True)
	ans = 0
	currSum = 0
	h = []
	for (i, j) in a:
		currSum += j
		heapq.heappush(h, j)
		if len(h) > k:
			currSum -= heapq.heappop(h)
		ans = max(ans, currSum * i)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
from heapq import *
(n, k) = map(int, input().split())
tb = [tuple(map(int, input().split())) for _ in range(n)]
tb.sort(key=lambda k: k[1], reverse=True)
pq = []
ans = 0
ts = 0
for i in range(k):
	heappush(pq, tb[i][0])
	ts += tb[i][0]
	ans = max(ans, ts * tb[i][1])
for i in range(k, n):
	if tb[i][0] > pq[0]:
		rem_t = heappop(pq)
		heappush(pq, tb[i][0])
		ts += tb[i][0] - rem_t
	ans = max(ans, ts * tb[i][1])
print(ans)


intin = lambda : map(int, input().split())
Ain = lambda : list(map(int, input().split()))
from _heapq import heappush, heappop
(n, k) = intin()
a = []
sm = 0
for I in range(n):
	(x, y) = intin()
	a.append([y, x])
a.sort(reverse=True)
h = []
ans = 0
for i in range(n):
	heappush(h, a[i][1])
	sm += a[i][1]
	tmp = 0
	if len(h) > k:
		tmp = heappop(h)
	sm -= tmp
	ans = max(ans, sm * a[i][0])
print(ans)


from heapq import heapify, heappop, heappush
(n, k) = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(n)]
data.sort(key=lambda x: -x[1])
ans = 0
heap = []
total_len = 0
for (i, j) in data:
	ans = max(ans, (total_len + i) * j)
	total_len += i
	heappush(heap, i)
	if len(heap) == k:
		total_len -= heap[0]
		heappop(heap)
print(ans)


import sys
import heapq
input = sys.stdin.readline
(n, k) = map(int, input().split())
l = []
for i in range(n):
	(a, b) = map(int, input().split())
	l.append((a, b))
l.sort(key=lambda x: x[1], reverse=True)
best = 0
curr = 0
q = []
for i in range(k):
	curr += l[i][0]
	heapq.heappush(q, l[i][0])
	best = max(best, curr * l[i][1])
for i in range(k, n):
	curr += l[i][0]
	heapq.heappush(q, l[i][0])
	curr -= heapq.heappop(q)
	best = max(best, curr * l[i][1])
print(best)


import bisect
import heapq
(n, k) = map(int, input().split())
li = []
for i in range(n):
	li.append(tuple(map(int, input().split())))
li.sort(key=lambda tup: -tup[1])
c = 0
l = []
ln = 0
for (a, b) in li:
	heapq.heappush(l, a)
	ln += a
	if len(l) > k:
		p = heapq.heappop(l)
		ln -= p
	if c < ln * b:
		c = ln * b
print(c)


import sys, heapq
printn = lambda x: sys.stdout.write(x)
DBG = not True

def ddprint(x):
	if DBG:
		print(x)
(n, k) = map(int, input().split())
t = []
b = []
a = []
for i in range(n):
	(ti, bi) = map(int, input().split())
	a.append((ti, bi))
a.sort(key=lambda x: -x[1])
ddprint(a)
mx = -1
lensum = 0
c = []
for i in range(n):
	(ti, bi) = a[i]
	if len(c) < k:
		heapq.heappush(c, ti)
		lensum += ti
	else:
		l = heapq.heappushpop(c, ti)
		lensum += ti - l
	mx = max(mx, lensum * bi)
print(mx)


import heapq
(n, k) = map(int, input().split())
l = []
for _ in range(n):
	(t, b) = map(int, input().split())
	l.append((b, t))
l = sorted(l, key=lambda x: x[0], reverse=True)
ans = 0
duration = 0
d = []
for (b, t) in l:
	duration += t
	heapq.heappush(d, t)
	if len(d) > k:
		c = heapq.heappop(d)
		duration -= c
	ans = max(ans, duration * b)
print(ans)


import sys
from collections import defaultdict
import heapq
strInp = lambda : input().strip().split()
intInp = lambda : list(map(int, strInp()))
(n, k) = intInp()
arr = []
li = []
for i in range(n):
	(l, b) = intInp()
	arr.append([l, b])
arr.sort(key=lambda x: x[1], reverse=True)
heapq.heapify(li)
ans = 0
s = 0
index = 1
for i in range(n):
	if index < k:
		heapq.heappush(li, arr[i][0])
		s += arr[i][0]
		ans = max(ans, arr[i][0] * arr[i][1], s * arr[i][1])
	else:
		heapq.heappush(li, arr[i][0])
		s += arr[i][0]
		ans = max(s * arr[i][1], ans)
		mi = heapq.heappop(li)
		s -= mi
	index += 1
print(ans)


import heapq
(n, k) = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(n)]
S.sort(key=lambda x: x[1], reverse=True)
ANS = 0
LENGTH = 0
H = []
for (x, y) in S:
	heapq.heappush(H, x)
	LENGTH += x
	if len(H) > k:
		z = heapq.heappop(H)
		LENGTH -= z
	if ANS < LENGTH * y:
		ANS = LENGTH * y
print(ANS)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		(t, b) = map(int, input().split())
		a.append((b, t))
	a.sort()
	cnt = 0
	ans = 0
	h = []
	for i in range(n - 1, -1, -1):
		heapq.heappush(h, a[i][1])
		cnt += a[i][1]
		while len(h) > k:
			cnt -= heapq.heappop(h)
		ans = max(ans, cnt * a[i][0])
	print(ans)
main()


from heapq import *
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, k) = kk()
ls = [None] * n
for i in range(n):
	ls[i] = tuple(kk())
ls.sort(key=lambda x: x[1])
(q, totall, m) = ([], 0, 0)
heapify(q)
for s in reversed(ls):
	if len(q) < k:
		heappush(q, s)
		totall += s[0]
	else:
		m = max(m, s[1] * (totall - q[0][0] + s[0]))
		if s[0] > q[0][0]:
			totall -= heappushpop(q, s)[0]
			totall += s[0]
	m = max(m, totall * s[1])
print(m)


from heapq import heappop, heappush
(n, k) = map(int, input().split())
d = []
for i in range(n):
	(t, b) = map(int, input().split())
	d.append((t, b))
d = sorted(d, key=lambda x: (x[1], x[0]), reverse=True)
num = 0
tmp = []
tmp2 = 0
for i in range(n):
	num = max(num, (tmp2 + d[i][0]) * d[i][1])
	heappush(tmp, d[i][0])
	tmp2 += d[i][0]
	if len(tmp) > k - 1:
		tmp2 -= heappop(tmp)
print(num)


import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
digl = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
import heapq
(n, k) = f()
l = []
for _ in range(n):
	(i, j) = f()
	l.append([i, j])
ans = 0
tl = 0
songs = []
l.sort(key=lambda x: x[1], reverse=True)
for (x, y) in l:
	heapq.heappush(songs, x)
	tl += x
	if len(songs) > k:
		p = heapq.heappop(songs)
		tl -= p
	ans = max(ans, tl * y)
print(ans)


from heapq import *
(n, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split()))[::-1])
a.sort(reverse=True)
ans = s = 0
t = []
for (i, j) in a:
	s += j
	heappush(t, j)
	if len(t) > k:
		s -= heappop(t)
	ans = max(ans, s * i)
print(ans)


import heapq
arr = input()
(N, K) = [int(x) for x in arr.split(' ')]
data = [[0] * 2 for _ in range(N)]
for i in range(N):
	arr = input()
	(L, B) = [int(x) for x in arr.split(' ')]
	data[i][0] = B
	data[i][1] = L
data.sort(reverse=True)
h = []
s = 0
res = 0
for i in range(N):
	if i < K:
		s += data[i][1]
		heapq.heappush(h, data[i][1])
	else:
		s += data[i][1]
		heapq.heappush(h, data[i][1])
		p = heapq.heappop(h)
		s -= p
	if s * data[i][0] > res:
		res = s * data[i][0]
print(res)


from heapq import *
(n, k) = list(map(int, input().split()))
a = []
for i in range(0, n):
	(b, p) = list(map(int, input().split()))
	a.append([p, b])
a.sort(reverse=True)
r = 0
s = 0
h = []
for (p, b) in a:
	s += b
	heappush(h, b)
	if len(h) > k:
		s -= heappop(h)
	r = max(r, s * p)
print(r)


import heapq
import sys
input = sys.stdin.buffer.readline
(n, k) = map(int, input().split())
list1 = []
for i in range(n):
	(length, beauty) = map(int, input().split())
	list1.append([length, beauty])
list1.sort(key=lambda x: -x[1])
heap = []
final_ans = 0
curr_length = 0
for i in range(k):
	heapq.heappush(heap, [list1[i][0]])
	curr_length += list1[i][0]
	final_ans = max(final_ans, curr_length * list1[i][1])
for i in range(k, n):
	p = heap[0]
	curr_length -= p[0]
	curr_length += list1[i][0]
	heapq.heapreplace(heap, [list1[i][0]])
	final_ans = max(final_ans, curr_length * list1[i][1])
print(final_ans)


import heapq
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(N, K) = map(int, input().split())
songs = [list(map(int, input().split())) for _ in range(N)]
songs = sorted(songs, key=lambda x: x[1], reverse=True)
ans = -float('inf')
S = []
tmpS = 0
for (t, v) in songs:
	if len(S) < K:
		heapq.heappush(S, t)
		tmpS += t
		minB = v
	elif S[0] <= t:
		tmpS = tmpS - S[0] + t
		heapq.heappop(S)
		heapq.heappush(S, t)
		minB = v
	ans = max(ans, minB * tmpS)
print(ans)


from heapq import *
(n, k) = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(n)]
l.sort(key=lambda x: x[1])
s = [0] * k
kmin = 0
sumi = 0
res = 0
for i in range(1, len(l) + 1):
	sumi += l[-i][0]
	heappush(s, l[-i][0])
	sumi -= heappop(s)
	res = max(res, sumi * l[-i][1])
print(res)


import heapq
(n, k) = map(int, input().split())
b_l = []
for _ in range(n):
	(t, b) = map(int, input().split())
	b_l.append([b, t])
b_l.sort(reverse=True)
ans = 0
sum_fg = 0
h = []
heapq.heapify(h)
for i in range(n):
	sum_fg += b_l[i][1]
	heapq.heappush(h, b_l[i][1])
	while len(h) > k:
		g = heapq.heappop(h)
		sum_fg -= g
	beauty = b_l[i][0]
	ans = max(ans, sum_fg * beauty)
print(ans)


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
from heapq import *
(n, k) = map(int, input().split())
S = []
for _ in range(n):
	(t, b) = map(int, input().split())
	S.append((t, b))
S.sort(key=lambda x: (-x[1], -x[0]))
(mb, st, cb) = (0, 0, 0)
pq = []
for (t, b) in S:
	st += t
	heappush(pq, (t, b))
	if len(pq) > k:
		(pt, pb) = heappop(pq)
		st -= pt
	mb = max(mb, st * b)
print(mb)


import heapq
R = lambda : map(int, input().split())
(n, k) = R()
L = []
for i in range(n):
	L.append(list(R()))
L = sorted(L, key=lambda x: x[1])
A = []
(res, p) = (0, 0)
for i in reversed(range(n)):
	p += L[i][0]
	heapq.heappush(A, L[i][0])
	if len(A) > k:
		p -= heapq.heappop(A)
	res = max(res, L[i][1] * p)
print(res)


from heapq import *
(n, k) = map(int, input().split())
l = []
la = []
for i in range(n):
	(a, b) = map(int, input().split())
	l.append([b, a])
l.sort()
l.reverse()
maxi = 0
h = []
s = 0
for i in range(n):
	(a, b) = (l[i][1], l[i][0])
	s += a
	heappush(h, a)
	if len(h) > k:
		d = heappop(h)
		s -= d
	maxi = max(maxi, b * s)
print(maxi)


import os
import sys
from io import BytesIO, IOBase
import heapq
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
(n, k) = rl()
beauty_length = []
for i in range(n):
	(t, b) = rl()
	beauty_length.append((b, t))
beauty_length.sort()
k_longuest = []
length = 0
ans = 0
for i in range(n):
	(b, t) = beauty_length.pop()
	if len(k_longuest) < k:
		heapq.heappush(k_longuest, t)
		length += t
		ans = max(ans, length * b)
	else:
		t_shortest = k_longuest[0]
		if t_shortest < t:
			heapq.heappop(k_longuest)
			heapq.heappush(k_longuest, t)
			length += t - t_shortest
			ans = max(ans, length * b)
print(ans)


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()
(n, k) = listIn()
(length, beauty) = ([], [])
for i in range(n):
	(t, b) = listIn()
	length.append(t)
	beauty.append((t, b))
beauty = sorted(beauty, key=lambda x: x[1])[::-1]
li = []
ans = 0
final = float('-inf')
for i in range(n):
	ele = beauty[i]
	b = ele[1]
	if i < k:
		ans += ele[0]
		heapq.heappush(li, ele[0])
	elif ele[0] > li[0]:
		ans += ele[0] - li[0]
		heapq.heappop(li)
		heapq.heappush(li, ele[0])
	final = max(final, ans * b)
print(final)


import heapq
(n, k) = list(map(int, input().split()))
tb = []
for i in range(n):
	tb.append(list(map(int, input().split())))
tb.sort(key=lambda x: x[1])
tb = tb[::-1]
l = []
s = 0
m = 0
for i in range(n):
	m = max(m, tb[i][0] * tb[i][1])
for i in range(n):
	heapq.heappush(l, tb[i][0])
	s = s + tb[i][0]
	if len(l) > k:
		s = s - heapq.heappop(l)
	m = max(m, tb[i][1] * s)
print(m)


import heapq
import sys
(n, k) = map(int, sys.stdin.readline().split())
p = []
for i in range(n):
	(t, b) = tuple(map(int, sys.stdin.readline().split()))
	p.append((b, t))
p.sort(reverse=True)
ans = 0
time = 0
a = []
for (b, t) in p:
	time += t
	heapq.heappush(a, t)
	if len(a) > k:
		c = heapq.heappop(a)
		time -= c
	ans = max(ans, time * b)
print(ans)


import sys
sys.setrecursionlimit(2000)
from collections import Counter
from functools import reduce
from itertools import combinations
import heapq

def solution1(n, k, songs):
	songs.sort(key=lambda x: x[1], reverse=True)
	heap = []
	best = 0
	length = 0
	for (l, height) in songs:
		length += l
		heapq.heappush(heap, l)
		if len(heap) > k:
			val = heapq.heappop(heap)
			length -= val
		best = max(best, length * height)
	return best

def brute_force(n, k, songs):
	best = 0
	for size in range(1, k + 1):
		for combo in combinations(songs, size):
			summ = sum([val[0] for val in combo])
			minn = min([val[1] for val in combo])
			best = max(best, minn * summ)
	return best

def validate():
	from random import seed
	from random import randint
	n = 10
	lmax = 100
	bmax = 100
	ntests = 25
	for test in range(ntests):
		seed(test)
		k = randint(1, n)
		songs = []
		for i in range(n):
			songs.append([randint(1, lmax), randint(1, bmax)])
		print('seed: %d' % test)
		val1 = solution1(n, k, songs)
		val2 = brute_force(n, k, songs)
		try:
			assert val1 == val2
			print('passed')
		except:
			print('failed', songs, val1, val2)
		print('')
(n, k) = [int(val) for val in sys.stdin.readline().split()]
songs = [[int(val) for val in sys.stdin.readline().split()] for song in range(n)]
print(solution1(n, k, songs))


import sys
import heapq

def rint():
	return list(map(int, sys.stdin.readline().split()))
(n, k) = rint()
t = []
b = []
ind = []
for i in range(n):
	(tt, bb) = rint()
	t.append(tt)
	b.append(bb)
	ind.append(i)
ind.sort(key=lambda i: (-b[i], -t[i]))
candi = 0
s = 0
cnt = 0
minb = 0
ans = 0
h = []
for i in range(n):
	bb = b[ind[i]]
	tt = t[ind[i]]
	if bb != minb:
		minb = bb
	heapq.heappush(h, (t[ind[i]], i))
	s += tt
	cnt += 1
	if cnt > k:
		(tc, ic) = heapq.heappop(h)
		s -= tc
		cnt -= 1
	candi = s * minb
	ans = max(candi, ans)
print(ans)


import heapq
(n, k) = map(int, input().split())
inp = []
for i in range(n):
	(t, b) = map(int, input().split())
	inp.append((b, t))
arr = sorted(inp, reverse=True)
time_heap = []
max_beauty = 0
current_time_sum = 0
for (b, t) in arr:
	current_time_sum += t
	heapq.heappush(time_heap, t)
	if len(time_heap) > k:
		least_time = heapq.heappop(time_heap)
		current_time_sum -= least_time
	max_beauty = max(max_beauty, current_time_sum * b)
print(max_beauty)


import os
import sys
from io import BytesIO, IOBase
from bisect import *

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	(n, k) = map(int, input().split())
	(a, c) = ([], [])
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		c.append(y)
	d = sorted(range(n), key=lambda x: c[x])
	b = SortedList()
	(su, ma) = (0, 0)
	for i in range(n - 1, -1, -1):
		su += a[d[i]]
		b.add(a[d[i]])
		while len(b) > k:
			su -= b[0]
			b.remove(b[0])
		ma = max(ma, su * c[d[i]])
	print(ma)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq
s = []
(n, k) = map(int, input().split())
for _ in range(n):
	(t, b) = map(int, input().split())
	s.append((t, b))
s.sort(key=lambda x: x[1], reverse=True)
t_max = t = s[0][0] * s[0][1]
i = 1
while i < k:
	t = (t // s[i - 1][1] + s[i][0]) * s[i][1]
	if t > t_max:
		t_max = t
	i += 1
h = [x[0] for x in s[:k]]
heapq.heapify(h)
for i in range(1, n - k + 1):
	sm = heapq.heappushpop(h, s[i + k - 1][0])
	t = (t // s[i - 2 + k][1] - sm + s[i + k - 1][0]) * s[i + k - 1][1]
	if t > t_max:
		t_max = t
print(t_max)


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
import heapq

def main():
	(n, k) = map(int, input().split())
	songs = []
	for _ in range(n):
		(t, b) = map(int, input().split())
		songs.append((b, t))
	songs.sort(reverse=True)
	ret = 0
	(curr_count, curr_sum) = (0, 0)
	h = []
	for i in range(n):
		(b, t) = songs[i]
		heapq.heappush(h, t)
		curr_sum += t
		curr_count += 1
		if curr_count > k:
			curr_sum -= heapq.heappop(h)
			curr_count -= 1
		ret = max(ret, curr_sum * b)
	print(ret)

def __starting_point():
	main()
__starting_point()


from heapq import heappush, heappop
(n, k) = map(int, input().split())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append([y, x])
a.sort(reverse=True)
heap = []
sumOfCurrPlaylist = 0
best = 0
for (beauty, length) in a:
	sumOfCurrPlaylist += length
	heappush(heap, length)
	if len(heap) > k:
		sumOfCurrPlaylist -= heappop(heap)
	best = max(best, sumOfCurrPlaylist * beauty)
print(best)


import bisect
import heapq
import math
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	(n, k) = mii()
	a = []
	for i in range(n):
		(x, y) = mii()
		a.append((y, x))
	a.sort(reverse=True)
	q = []
	ans = 0
	s = 0
	for i in a:
		s += i[1]
		heapq.heappush(q, i[1])
		if len(q) > k:
			c = heapq.heappop(q)
			s -= c
		ans = max(ans, s * i[0])
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
from heapq import *
(n, k) = map(int, input().split())
(t, b) = ([], [])
for _ in range(n):
	(tt, bb) = map(int, input().split())
	t.append(tt)
	b.append(bb)
songs = sorted(list(zip(b, t)))
mxsum = [songs[-1][1]]
h = []
heappush(h, mxsum[0])
cnt = 1
sm = mxsum[0]
for i in range(n - 2, -1, -1):
	heappush(h, songs[i][1])
	sm += songs[i][1]
	cnt += 1
	if cnt > k:
		sm -= heappop(h)
	mxsum.append(sm)
mxsum = mxsum[::-1]
print(max((s[0] * tt for (s, tt) in zip(songs, mxsum))))


from operator import itemgetter
from heapq import heappush, heappushpop
import sys
(N, K) = map(int, input().split())
TB = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
TB.sort(key=itemgetter(1), reverse=True)
Q = []
sumi = 0
ans = 0
for (t, b) in TB[:K]:
	sumi += t
	heappush(Q, t)
	ans = max(ans, sumi * b)
for (t, b) in TB[K:]:
	sumi += t - heappushpop(Q, t)
	ans = max(ans, sumi * b)
print(ans)


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
from heapq import heappush as hp
from heapq import heappop as hhp
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
(n, k) = ri()
a = []
for i in range(n):
	(u, v) = ri()
	a.append((v, u))
a.sort(reverse=True)
ans = 0
l = []
cur = 0
pos = 0
while pos < n:
	if len(l) == k:
		cur -= hhp(l)
	hp(l, a[pos][1])
	cur += a[pos][1]
	ans = max(ans, cur * a[pos][0])
	pos += 1
print(ans)


import heapq
(n, k) = map(int, input().strip().split())
playlist = []
for i in range(n):
	(t, b) = map(int, input().strip().split())
	playlist.append((b, t))
playlist.sort(reverse=True)
(ans, sumt, d_set) = (0, 0, [])
for (b, t) in playlist:
	sumt += t
	heapq.heappush(d_set, t)
	if len(d_set) > k:
		sumt -= heapq.heappop(d_set)
	ans = max(ans, sumt * b)
print(ans)


from sys import stdin
import heapq as hp
(n, k) = map(int, stdin.readline().strip().split())
s = []
for i in range(n):
	(a, b) = map(int, stdin.readline().strip().split())
	s.append((b, a))
s.sort(reverse=True)
s1 = []
sm = 0
ans = 0
for i in range(k):
	sm += s[i][1]
	hp.heappush(s1, s[i][1])
	ans = max(sm * s[i][0], ans)
for i in range(k, n):
	x = hp.heappop(s1)
	if s[i][1] > x:
		sm -= x
		sm += s[i][1]
		hp.heappush(s1, s[i][1])
	else:
		hp.heappush(s1, x)
	ans = max(ans, sm * s[i][0])
print(ans)


import heapq
(n, k) = map(int, input().split())
ar = []
for i in range(n):
	ar.append(list(map(int, input().split())))
ar.sort(key=lambda x: x[1])
tem = []
su = 0
ans = 0
for i in range(min(k, n)):
	su += ar[-(i + 1)][0]
	tem.append(ar[-(i + 1)][0])
	ans = max(ans, ar[-(i + 1)][1] * su)
heapq.heapify(tem)
for i in range(k, n):
	yy = ar[-(i + 1)][0]
	xx = heapq.heappushpop(tem, yy)
	su += yy - xx
	ans = max(ans, ar[-(i + 1)][1] * su)
print(ans)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
from heapq import heappush, heappop
(n, k) = mi()
a = [li() for i in range(n)]
a = sorted(((b, t) for (t, b) in a))
h = []
ans = sm = 0
for (b, t) in a[::-1]:
	sm += t
	heappush(h, t)
	if len(h) > k:
		sm -= heappop(h)
	ans = max(ans, sm * b)
print(ans)


import sys
input = sys.stdin.buffer.readline
from heapq import heappop, heappush, heapify
(n, k) = map(int, input().split())
he = []
heapify(he)
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append([y, x])
a.sort(reverse=True)
ans = 0
count = 0
add = 1
for i in range(n):
	if add > k and he[0] >= a[i][1]:
		continue
	if add > k:
		count -= he[0]
		heappop(he)
	count += a[i][1]
	heappush(he, a[i][1])
	ans = max(ans, count * a[i][0])
	add += 1
print(ans)


import heapq
d = []
(n, k) = [int(x) for x in input().split()]
c = []
lena = 0
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	c.append((b, a))
c.sort(reverse=True)
answer = []
summa = 0
for item in c:
	if lena >= k:
		a = heapq.heappop(d)
		summa -= a
		heapq.heappush(d, max(item[1], a))
		summa += max(item[1], a)
	else:
		heapq.heappush(d, item[1])
		summa += item[1]
		lena += 1
	answer.append(summa * item[0])
print(max(answer))


import heapq
(n, k) = map(int, input().split())
t = []
b = []
a = []
for i in range(n):
	(ti, bi) = map(int, input().split())
	a.append((ti, bi))
a.sort(key=lambda x: -x[1])
mx = -1
lens = 0
c = []
for i in range(n):
	(ti, bi) = a[i]
	if len(c) < k:
		heapq.heappush(c, ti)
		lens += ti
	else:
		l = heapq.heappushpop(c, ti)
		lens += ti - l
	mx = max(mx, lens * bi)
print(mx)


from heapq import heappush, heappop
h = []
(n, k) = map(int, input().strip().split())
l = []
for i in range(n):
	(t, b) = map(int, input().strip().split())
	l.append([b, t])
l.sort()
ans = 0
sm = 0
for i in range(n - 1, -1, -1):
	heappush(h, l[i][1])
	sm += l[i][1]
	if len(h) > k:
		sm -= heappop(h)
	ans = max(ans, l[i][0] * sm)
print(ans)


from heapq import heappush, heappop
import sys
(n, k) = map(int, input().split())
songs = sorted(map(lambda x: (int(x[1]), int(x[0])), map(str.split, sys.stdin)), reverse=True)
ans = 0
total_current_duration = 0
heap = []
for (beauty, duration) in songs:
	total_current_duration += duration
	heappush(heap, duration)
	if len(heap) > k:
		total_current_duration -= heappop(heap)
	ans = max(ans, total_current_duration * beauty)
print(ans)


import heapq
(n, k) = map(int, input().split())
a = sorted(tuple((list(map(int, input().split())) for i in range(n))), key=lambda x: x[1], reverse=True)
time = []
m = 0
s = 0
for (t, b) in a:
	s += t
	heapq.heappush(time, t)
	if len(time) > k:
		s -= heapq.heappop(time)
	m = max(m, s * b)
print(m)


import heapq
(n, k) = map(int, input().split())
a = []
for j in range(n):
	(u, v) = map(int, input().split())
	a.append([v, u])
a.sort(reverse=True)
s = 0
h = []
p = 0
for (v, u) in a:
	s = s + u
	heapq.heappush(h, u)
	if len(h) > k:
		s = s - heapq.heappop(h)
	p = max(p, s * v)
print(p)


import heapq
(n, k) = map(int, input().split())
songs = [(0, 0) for i in range(n)]
for i in range(n):
	songs[i] = tuple(map(int, input().split()))
songs.sort(key=lambda x: x[1], reverse=True)
heap = []
max_ = 0
length = 0
for i in range(n):
	if i >= k:
		l = heapq.heappushpop(heap, songs[i][0])
		length = length - l + songs[i][0]
	else:
		length += songs[i][0]
		heapq.heappush(heap, songs[i][0])
	max_ = max(max_, length * songs[i][1])
print(max_)


import heapq
(n, k) = map(int, input().split())
songs = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])
ans = -float('inf')
S = []
tmpS = 0
for (t, v) in songs:
	if len(S) < k:
		heapq.heappush(S, t)
		tmpS += t
		minB = v
	else:
		tmp = heapq.heappop(S)
		if tmp < t:
			tmpS = tmpS - tmp + t
			heapq.heappush(S, t)
			minB = v
		else:
			heapq.heappush(S, tmp)
			minB = v
	ans = max(ans, minB * tmpS)
print(ans)


import heapq
(N, K) = map(int, input().split())
songs = []
for n in range(N):
	(t, b) = map(int, input().split())
	songs.append((b, t))
songs.sort(reverse=True)
ans = 0
tlen = 0
theap = []
for (b, t) in songs:
	tlen += t
	heapq.heappush(theap, t)
	while len(theap) > K:
		x = heapq.heappop(theap)
		tlen -= x
	ans = max(ans, tlen * b)
print(ans)


import heapq as q
(n, k) = [int(x) for x in input().split()]
h = []
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
a.sort(reverse=True, key=lambda x: x[1])
s = 0
ans = 0
for (l, r) in a:
	s += l
	q.heappush(h, l)
	if len(h) > k:
		s -= q.heappop(h)
	ans = max(ans, s * r)
print(ans)


import heapq
(n, k) = input().split()
n = int(n)
k = int(k)
v = []
aux = []
ans = 0
soma = 0
for i in range(0, n):
	(t, b) = input().split()
	t = int(t)
	b = int(b)
	v.append((b, t))
v.sort()
for i in range(n - 1, -1, -1):
	soma += v[i][1]
	heapq.heappush(aux, v[i][1])
	while len(aux) > k:
		soma -= heapq.heappop(aux)
	ans = max(ans, soma * v[i][0])
print(ans)


import heapq
(n, k) = map(int, input().split())
tb = []
for i in range(n):
	(u, v) = map(int, input().split())
	tb.append([u, v])
tb.sort(key=lambda x: x[1])
t = [i[0] for i in tb]
b = [i[1] for i in tb]
su = 0
m = 0
i = n - 1
while i >= n - k:
	su += t[i]
	m = max(m, su * b[i])
	i -= 1
d = t[n - k:]
heapq.heapify(d)
while i > -1:
	heapq.heappush(d, t[i])
	su = su + t[i] - heapq.heappop(d)
	m = max(m, su * b[i])
	i -= 1
print(m)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, k) = LI()
	aa = sorted([LI() for _ in range(n)], key=lambda x: [-x[1], -x[0]])
	q = []
	r = 0
	s = 0
	for (t, b) in aa:
		heapq.heappush(q, t)
		s += t
		if len(q) > k:
			s -= heapq.heappop(q)
		tr = s * b
		if r < tr:
			r = tr
	return r
print(main())


from heapq import *
(n, k) = map(int, input().split())
bt = sorted(list(map(lambda _: (_[1], _[0]), [tuple(map(int, input().split())) for i in range(n)])), reverse=True)
(ans, tl, hp) = (0, 0, [])
for i in range(n):
	tl += bt[i][1]
	heappush(hp, bt[i][1])
	if i >= k:
		tl -= heappop(hp)
	ans = max(ans, bt[i][0] * tl)
print(ans)


import heapq as hp
import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
(n, k) = map(int, input().split())
a = []
for i in range(n):
	(x, y) = map(int, I().split())
	a.append([y, x])
a.sort(reverse=True)
ma = -1
c = 0
s = 0
h = []
for i in a:
	c += 1
	(x, y) = (i[1], i[0])
	if c <= k:
		s += x
		ma = max(s * y, ma)
		hp.heappush(h, x)
	else:
		if x > h[0]:
			s += x
			s -= hp.heappop(h)
			hp.heappush(h, x)
		ma = max(s * y, ma)
print(ma)


import os, sys
from io import BytesIO, IOBase
from heapq import *

def main():
	(n, k) = map(int, input().split())
	(le, be) = ([], [])
	for _ in range(n):
		(a, b) = map(int, input().split())
		le.append(a)
		be.append(b)
	rr = sorted(range(n), key=lambda xx: le[xx], reverse=1)
	(su, mini, ans, he) = (0, 10 ** 9, 0, [])
	for i in rr:
		su += le[i]
		mini = min(mini, be[i])
		heappush(he, (be[i], le[i]))
		ans = max(ans, su * mini)
		if len(he) == k:
			while len(he):
				(a, b) = he[0]
				if a != mini:
					break
				heappop(he)
				su -= b
			mini = he[0][0] if len(he) else 10 ** 9
			ans = max(ans, su * mini)
	while len(he):
		while len(he):
			(a, b) = he[0]
			if a != mini:
				break
			heappop(he)
			su -= b
		mini = he[0][0] if len(he) else 10 ** 9
		ans = max(ans, su * mini)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq
(n, k) = map(int, input().split())
bt = []
for i in range(n):
	(t, b) = map(int, input().split())
	bt.append((b, t))
bt.sort(reverse=True)
h = []
heapq.heappush(h, bt[0][1])
leng = bt[0][1]
minb = bt[0][0]
ans = leng * minb
for i in range(1, n):
	if len(h) < k:
		heapq.heappush(h, bt[i][1])
		leng += bt[i][1]
	else:
		popd = heapq.heappushpop(h, bt[i][1])
		leng = leng + bt[i][1] - popd
	minb = bt[i][0]
	if leng * minb > ans:
		ans = leng * minb
print(ans)


from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, k) = gil()
ans = -inf
m = []
for _ in range(n):
	(a, b) = gil()
	ans = max(a * b, ans)
	m.append((b, a))
m.sort()
h = []
cv = 0
for i in reversed(range(n)):
	ans = max(ans, m[i][0] * (cv + m[i][1]))
	heappush(h, m[i][1])
	cv += m[i][1]
	if len(h) >= k:
		cv -= heappop(h)
print(ans)


import sys
import heapq
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
(nb_songs, choose) = RMI()
songval = []
for _ in range(nb_songs):
	songval.append(RMI())
songval.sort(key=lambda x: -x[1])
maxs = min_val
lsum = 0
choice = []
for i in range(nb_songs):
	(ti, bi) = songval[i]
	if len(choice) < choose:
		heapq.heappush(choice, ti)
		lsum += ti
	else:
		l = heapq.heappushpop(choice, ti)
		lsum += ti - l
	maxs = max(maxs, lsum * bi)
print(maxs)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq
(n, k) = map(int, input().split())
q = []
for i in range(n):
	(u, v) = map(int, input().split())
	q.append((v, u))
a = []
q = sorted(q)[::-1]
ans = 0
time = 0
for (b, t) in q:
	time += t
	heapq.heappush(a, t)
	if len(a) > k:
		var = heapq.heappop(a)
		time -= var
	ans = max(ans, time * b)
print(ans)