Неужели нам действительно нужно объяснять правила Balatro? Просто сыграйте сами. И не забудьте остановиться до начала следующего контеста.
Для тех, кто не знаком с правилами: у вас на руках есть $n$ карт. Каждой карте сопоставлены два значения: $a_i$ и $b_i$. Вы можете выбрать любое подмножество $S$ из ровно $k$ карт и сыграть их вместе, получив количество очков, вычисляемое по формуле:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Ваша задача — определить максимально возможное количество очков, которое можно набрать за один ход, используя ровно $k$ карт.
Дополнительно известно, что колода сбалансирована, то есть ни у одной карты значения $a_i$ и $b_i$ не могут быть слишком большими одновременно. А именно, для каждой карты выполняется $\min(a_i, b_i) \le 100$.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных начинается со строки, содержащей два целых числа $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$) — общее количество карт и количество карт, которые нужно выбрать для одного хода.
Каждая из следующих $n$ строк содержит два целых числа $a_i$ и $b_i$ ($1 \le a_i, b_i \le 10^9$), обозначающих параметры карты. Для каждой карты выполняется $\min(a_i, b_i) \le 100$.
Суммарное количество карт по всем наборам входных данных не превосходит $10^5$.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное количество очков, которое можно получить, выбрав ровно $k$ карт.
Примеры
Входные данные 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Выходные данные 1
225
Входные данные 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Выходные данные 2
400
Примечание
В первом наборе входных данных мы используем все карты. Количество очков равно $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Во втором наборе входных данных нам нужно отбросить одну карту. Набор из карт $[2, 3, 4, 5, 6]$ даёт значение $400$.
Интересный факт: в настоящей игре Balatro значение $a_i$ карты основано на её покерном достоинстве, а $b_i$ может быть равно $0$, $4$ или $20$ ($20$ выпадает с вероятностью $20\%$). Кроме того, существуют сотни бонусных карт и правил, влияющих на то, как вычисляются суммы $a$ и $b$.