Måste vi verkligen förklara reglerna för Balatro? Spela det bara själv. Och kom ihåg att sluta före nästa tävling.
För dem som inte kan reglerna: du har $n$ kort på handen. Varje kort har två tillhörande värden: $a_i$ och $b_i$. Du kan välja en godtycklig delmängd $S$ med exakt $k$ kort och spela dem tillsammans för att få en poäng som beräknas som:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Din uppgift är att bestämma den högsta möjliga poängen du kan uppnå i ett enda drag med exakt $k$ kort.
Det är dessutom känt att kortleken är balanserad, vilket innebär att inget kort har både $a_i$ och $b_i$ samtidigt för höga. Specifikt gäller för varje kort att $\min(a_i, b_i) \le 100$.
Indata
Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $t$ ($1 \le t \le 10^4$). Beskrivningen av testfallen följer.
Varje testfall börjar med en rad som innehåller två heltal $n$ och $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): det totala antalet kort och antalet kort som ska väljas för ett enda drag.
Var och en av de följande $n$ raderna innehåller två heltal $a_i$ och $b_i$ ($1 \le a_i, b_i \le 10^9$), som representerar värdena på ett kort. För varje kort gäller $\min(a_i, b_i) \le 100$.
Det totala antalet kort över alla testfall överstiger inte $10^5$.
Utdata
För varje testfall, skriv ut ett enda heltal: den högsta möjliga poängen som kan erhållas genom att välja exakt $k$ kort.
Exempel
Indata 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Utdata 1
225
Indata 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Utdata 2
400
Förklaring
I det första testfallet använder vi alla kort. Poängen är $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
I det andra testfallet måste vi välja bort ett kort. Mängden med korten $[2, 3, 4, 5, 6]$ har värdet $400$.
Kuriosa: I det riktiga spelet Balatro baseras $a_i$ för ett kort på dess poker-värde, och $b_i$ kan vara $0$, $4$ eller $20$ ($20$ kan inträffa med $20\%$ sannolikhet). Dessutom finns det hundratals bonuskort och regler som påverkar hur summorna av $a$ och $b$ beräknas.