В самый крупный магазин Берляндии поступила партия елей. В магазин уже пришли \(n\) клиентов, которые хотят их купить.
Перед началом продаж магазину осталось определиться с ценой за одну елку (цена одинакова для всех покупателей). Для этого у магазина есть некоторая информация о каждом клиенте.
Для \(i\)-го клиента известно два целых числа \(a_i\) и \(b_i\), которые определяют его поведение:
- если цена товара не более \(a_i\), то клиент купит елку и оставит положительный отзыв;
- иначе, если цена товара не более \(b_i\), то клиент купит елку, но оставит отрицательный отзыв;
- иначе клиент не будет покупать елку вообще.
Ваша задача — посчитать максимально возможный заработок магазина, если можно получить не более \(k\) отрицательных отзывов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможный заработок магазина, если можно получить не более \(k\) отрицательных отзывов.
Примечание
Рассмотрим пример из условия:
- в первом наборе входных данных надо поставить цену, равную \(1\). Тогда оба клиента купят по одной елке и не оставят ни одного отрицательного отзыва;
- во втором наборе входных данных надо поставить цену, равную \(5\). Тогда единственный клиент купит елку и оставит отрицательный отзыв;
- в третьем наборе входных данных надо поставить цену, равную \(3\). Тогда все клиенты купят по одной елке, и магазин получит два отрицательных отзыва.
- в четвертом наборе входных данных надо поставить цену, равную \(7\). Тогда два клиента купят по одной елке, и магазин получит один отрицательный отзыв.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 0
2 1
3 4
1 1
2
5
3 3
1 5 2
3 6 4
4 3
2 3 2 8
3 7 3 9
3 1
2 9 5
12 14 9
|
2
5
9
14
15
|