В вашем плейлисте есть \(n\) песен. \(i\)-я песня характеризуется двумя числами \(t_i\) и \(b_i\) — длиной и красотой соответственно. Удовольствие от прослушивания множества песен равно суммарной длине этих песен умноженной на минимальную красоту среди них. Например, удовольствие от прослушивания \(3\) песен с длинами \([5, 7, 4]\) и красотами \([11, 14, 6]\) равна \((5 + 7 + 4) \cdot 6 = 96\).
Вам нужно выбрать не более \(k\) песен из вашего плейлиста так, чтобы максимизировать удовольствие от их прослушивания.
Выходные данные
Выведите одно число — максимальное удовольствие, которое вы можете получить.
Примечание
В первом тестовом примере вам нужно выбрать песни \({1, 3, 4}\), и удовольствие будет равно \((4 + 3 + 6) \cdot 6 = 78\).
Во втором тестовом примере нужно просто выбрать песню под номером \(3\). Удоволоствие от неё будет равно \(100 \cdot 100 = 10000\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
4 7
15 1
3 6
6 8
|
78
|
|
2
|
5 3
12 31
112 4
100 100
13 55
55 50
|
10000
|