Þurfum við virkilega að útskýra reglurnar í Balatro? Prófaðu bara að spila hann sjálf(ur). Og mundu að hætta fyrir næstu keppni.
Fyrir þá sem þekkja ekki reglurnar: þú ert með $n$ spil á hendi. Hvert spil hefur tvö tengd gildi: $a_i$ og $b_i$. Þú getur valið hvaða hlutmengi $S$ sem er af nákvæmlega $k$ spilum og spilað þeim út saman til að fá stig sem reiknuð eru sem:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Verkefni þitt er að ákvarða hæsta mögulega stigafjölda sem þú getur náð í einni útspilun með því að nota nákvæmlega $k$ spil.
Auk þess er vitað að stokkurinn er í jafnvægi, sem þýðir að ekkert spil hefur bæði $a_i$ og $b_i$ of há á sama tíma. Nánar tiltekið gildir fyrir hvert spil að $\min(a_i, b_i) \le 100$.
Inntak
Hvert próf inniheldur mörg prófunartilfelli. Fyrsta línan inniheldur fjölda prófunartilfella $t$ ($1 \le t \le 10^4$). Lýsing á prófunartilfellunum fylgir.
Hvert prófunartilfelli byrjar á línu sem inniheldur tvær heiltölur $n$ og $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): heildarfjölda spila og fjölda spila sem á að velja fyrir eina útspilun.
Hver af næstu $n$ línum inniheldur tvær heiltölur $a_i$ og $b_i$ ($1 \le a_i, b_i \le 10^9$), sem tákna gildi spils. Fyrir hvert spil gildir $\min(a_i, b_i) \le 100$.
Heildarfjöldi spila yfir öll prófunartilfelli fer ekki yfir $10^5$.
Úttak
Fyrir hvert prófunartilfelli skal prenta eina heiltölu: hæsta mögulega stigafjölda sem hægt er að fá með því að velja nákvæmlega $k$ spil.
Dæmi
Inntak 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Úttak 1
225
Inntak 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Úttak 2
400
Skýring
Í fyrsta prófunartilfellinu notum við öll spilin. Stigin eru $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Í öðru prófunartilfellinu verðum við að sleppa einu spili. Mengið með spilunum $[2, 3, 4, 5, 6]$ hefur gildið $400$.
Skemmtileg staðreynd: Í alvöru Balatro leiknum byggist $a_i$ á póker-gildi spilsins, og $b_i$ getur verið $0$, $4$ eða $20$ ($20$ getur komið fyrir með $20\%$ líkum). Einnig eru hundruð bónusspila og reglna sem hafa áhrif á hvernig summur $a$ og $b$ eru reiknaðar.