Невже нам справді потрібно пояснювати правила 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$.