Рабочее место участника

Доктор Манхэттен решил построить город на Марсе из `K` домов. Каждый дом должен быть построен по собственному уникальному проекту, который выбирается среди `N` проектов. Все проекты предусматривают строительство домов прямоугольной формы, но размеры домов различны – по `i`-му проекту дом имеет ширину `W_i` и высоту `H_i`. Дома строятся на одной линии, рядом друг с другом. После строительства город закрывается куполом, который имеет прямоугольную форму, и заполняется воздухом. Так как доставка воздуха с Земли слишком сложна, то нужно минимизировать размер купола.

Напишите программу, которая выберет `K` проектов для домов из `N` проектов таким образом, чтобы необходимый объем воздуха для заполнения купола (произведение ширины купола на его высоту) был минимальным.

Для первого примера минимальный объем (20 единиц) получается при выборе следующих 3 домов:

Первая строка ввода содержит два целых числа – количество проектов `N` и количество домов `K` (`1\ ≤\ K\ ≤\ N\ ≤\ 1\ 000\ 000`). Следующие `N` строк содержат по два целых числа – ширина `W_i` и высота `H_i` дома по `i`-му проекту (`1\ ≤\ W_i,\ H_i\ ≤\ 1\ 000\ 000`). Все пары `(W_i,\ H_i)` различны.

Вывести одно целое число – минимальный объем воздуха для заполнения купола.

4 3
2 3
2 2
1 4
3 2

20

3 3
1 1
3 3
2 2

18

4 1
6 4
4 5
19 1
3 6

18