Må vi virkelig forklare reglene i Balatro? Bare spill det selv. Og husk å stoppe før neste konkurranse.
For dem som ikke kjenner reglene: du har $n$ kort på hånden. Hvert kort har to tilhørende verdier: $a_i$ og $b_i$. Du kan velge en hvilken som helst delmengde $S$ med nøyaktig $k$ kort og spille dem sammen for å oppnå en poengsum som beregnes som:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Oppgaven din er å finne den maksimale poengsummen du kan oppnå i ett enkelt trekk ved å bruke nøyaktig $k$ kort.
Det er i tillegg kjent at kortstokken er balansert, noe som betyr at ingen kort har både $a_i$ og $b_i$ samtidig for høye. Spesifikt gjelder det for hvert kort at $\min(a_i, b_i) \le 100$.
Inndata
Hver test inneholder flere testtilfeller. Den første linjen inneholder antallet testtilfeller $t$ ($1 \le t \le 10^4$). Beskrivelsen av testtilfellene følger.
Hvert testtilfelle begynner med en linje som inneholder to heltall $n$ og $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): det totale antallet kort og antallet kort som skal velges for ett enkelt trekk.
Hver av de neste $n$ linjene inneholder to heltall $a_i$ og $b_i$ ($1 \le a_i, b_i \le 10^9$), som representerer verdiene til et kort. For hvert kort gjelder $\min(a_i, b_i) \le 100$.
Det totale antallet kort over alle testtilfeller overstiger ikke $10^5$.
Utdata
For hvert testtilfelle skal du skrive ut ett enkelt heltall: den maksimale poengsummen som kan oppnås ved å velge nøyaktig $k$ kort.
Eksempler
Inndata 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Utdata 1
225
Inndata 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Utdata 2
400
Forklaring
I det første testtilfellet bruker vi alle kortene. Poengsummen er $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
I det andre testtilfellet må vi droppe ett kort. Mengden med kortene $[2, 3, 4, 5, 6]$ har verdien $400$.
Morsomt fakta: I det virkelige spillet Balatro er $a_i$ for et kort basert på poker-verdien til kortet, og $b_i$ kan være $0$, $4$ eller $20$ ($20$ kan forekomme med $20\%$ sjanse). I tillegg finnes det hundrevis av bonuskort og regler som påvirker hvordan summene av $a$ og $b$ beregnes.