Müssen wir wirklich die Regeln von Balatro erklären? Spiel es einfach selbst. Und denk daran, vor dem nächsten Wettbewerb wieder aufzuhören.
Für alle, die mit den Regeln nicht vertraut sind: Du hast $n$ Karten auf der Hand. Jede Karte hat zwei zugehörige Werte: $a_i$ und $b_i$. Du kannst eine beliebige Teilmenge $S$ aus genau $k$ Karten auswählen und sie zusammen ausspielen, um eine Punktzahl zu erhalten, die wie folgt berechnet wird:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Deine Aufgabe ist es, die maximal mögliche Punktzahl zu bestimmen, die du in einem einzigen Spielzug mit genau $k$ Karten erreichen kannst.
Zusätzlich ist bekannt, dass das Kartendeck ausgewogen ist, was bedeutet, dass bei keiner Karte $a_i$ und $b_i$ gleichzeitig zu hoch sind. Konkret gilt für jede Karte $\min(a_i, b_i) \le 100$.
Eingabe
Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $t$ ($1 \le t \le 10^4$). Es folgt die Beschreibung der Testfälle.
Jeder Testfall beginnt mit einer Zeile mit zwei ganzen Zahlen $n$ und $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): der Gesamtzahl der Karten und der Anzahl der Karten, die für einen einzelnen Spielzug ausgewählt werden müssen.
Jede der nächsten $n$ Zeilen enthält zwei ganze Zahlen $a_i$ und $b_i$ ($1 \le a_i, b_i \le 10^9$), die die Werte einer Karte darstellen. Für jede Karte gilt $\min(a_i, b_i) \le 100$.
Die Gesamtzahl der Karten über alle Testfälle hinweg überschreitet nicht $10^5$.
Ausgabe
Gib für jeden Testfall eine einzige ganze Zahl aus: die maximal mögliche Punktzahl, die durch Auswahl von genau $k$ Karten erzielt werden kann.
Beispiele
Eingabe 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Ausgabe 1
225
Eingabe 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Ausgabe 2
400
Hinweis
Im ersten Testfall verwenden wir alle Karten. Die Punktzahl beträgt $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Im zweiten Testfall müssen wir eine Karte weglassen. Die Menge mit den Karten $[2, 3, 4, 5, 6]$ hat den Wert $400$.
Wissenswertes: Im echten Spiel Balatro basiert der Wert $a_i$ einer Karte auf ihrem Poker-Wert, und $b_i$ kann $0$, $4$ oder $20$ sein ($20$ tritt mit einer Wahrscheinlichkeit von $20\%$ auf). Außerdem gibt es Hunderte von Bonuskarten und Regeln, die beeinflussen, wie die Summen von $a$ und $b$ berechnet werden.