Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Плейлист
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В вашем плейлисте есть $$$n$$$ песен. $$$i$$$-я песня характеризуется двумя числами $$$t_i$$$ и $$$b_i$$$ — длиной и красотой соответственно. Удовольствие от прослушивания множества песен равно суммарной длине этих песен умноженной на минимальную красоту среди них. Например, удовольствие от прослушивания $$$3$$$ песен с длинами $$$[5, 7, 4]$$$ и красотами $$$[11, 14, 6]$$$ равна $$$(5 + 7 + 4) \cdot 6 = 96$$$.

Вам нужно выбрать не более $$$k$$$ песен из вашего плейлиста так, чтобы максимизировать удовольствие от их прослушивания.

Входные данные

Первая строка содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) – количество песен в плейлисте и максимальное количество песен, которое вы можете выбрать.

Каждая из следующих $$$n$$$ строк содержит по два числа $$$t_i$$$ и $$$b_i$$$ ($$$1 \le t_i, b_i \le 10^6$$$) — длина и красота $$$i$$$-й песни.

Выходные данные

Выведите одно число — максимальное удовольствие, которое вы можете получить.

Примеры
Входные данные
4 3
4 7
15 1
3 6
6 8
Выходные данные
78
Входные данные
5 3
12 31
112 4
100 100
13 55
55 50
Выходные данные
10000
Примечание

В первом тестовом примере вам нужно выбрать песни $$${1, 3, 4}$$$, и удовольствие будет равно $$$(4 + 3 + 6) \cdot 6 = 78$$$.

Во втором тестовом примере нужно просто выбрать песню под номером $$$3$$$. Удоволоствие от неё будет равно $$$100 \cdot 100 = 10000$$$.