Czy naprawdę musimy tłumaczyć zasady gry Balatro? Po prostu sam w nią zagraj. I pamiętaj, żeby przestać przed następnymi zawodami.
Dla osób niezaznajomionych z zasadami: masz w ręku $n$ kart. Każda karta ma dwie przypisane wartości: $a_i$ oraz $b_i$. Możesz wybrać dowolny podzbiór $S$ składający się z dokładnie $k$ kart i zagrać je razem, uzyskując wynik obliczany jako:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Twoim zadaniem jest wyznaczenie maksymalnego możliwego wyniku, jaki możesz osiągnąć w jednym zagraniu, używając dokładnie $k$ kart.
Dodatkowo wiadomo, że talia jest zbalansowana, co oznacza, że żadna karta nie ma jednocześnie zbyt dużych wartości $a_i$ oraz $b_i$. Dokładniej, dla każdej karty zachodzi $\min(a_i, b_i) \le 100$.
Wejście
Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^4$). Następnie podane są opisy kolejnych przypadków testowych.
Każdy przypadek testowy zaczyna się od wiersza zawierającego dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): łączną liczbę kart oraz liczbę kart do wybrania w jednym zagraniu.
Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i, b_i \le 10^9$), oznaczające wartości karty. Dla każdej karty zachodzi $\min(a_i, b_i) \le 100$.
Łączna liczba kart we wszystkich przypadkach testowych nie przekracza $10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: maksymalny możliwy wynik, jaki można uzyskać, wybierając dokładnie $k$ kart.
Przykład
Wejście 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Wyjście 1
225
Wejście 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Wyjście 2
400
Uwagi
W pierwszym przypadku testowym używamy wszystkich kart. Wynik wynosi $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
W drugim przypadku testowym musimy odrzucić jedną kartę. Zbiór kart $[2, 3, 4, 5, 6]$ daje wartość $400$.
Ciekawostka: W prawdziwej grze Balatro wartość $a_i$ karty zależy od jej wartości pokerowej, a $b_i$ może wynosić $0$, $4$ lub $20$ ($20$ wypada z prawdopodobieństwem $20\%$). Ponadto istnieją setki kart bonusowych i zasad wpływających na sposób obliczania sum wartości $a$ oraz $b$.