Täytyykö meidän muka oikeasti selittää Balatron säännöt? Pelaa sitä itse. Ja muista lopettaa ennen seuraavaa kilpailua.
Niille, joille säännöt eivät ole tutut: sinulla on kädessäsi $n$ korttia. Jokaiseen korttiin liittyy kaksi arvoa: $a_i$ ja $b_i$. Voit valita minkä tahansa täsmälleen $k$ kortin osajoukon $S$ ja pelata ne yhdessä, jolloin saat pistemäärän, joka lasketaan seuraavasti:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Tehtäväsi on määrittää suurin mahdollinen pistemäärä, jonka voit saavuttaa yhdellä pelauksella käyttäen täsmälleen $k$ korttia.
Lisäksi tiedetään, että pakka on tasapainoinen, mikä tarkoittaa, ettei millään kortilla ole samanaikaisesti liian suuria arvoja $a_i$ ja $b_i$. Tarkemmin sanottuna jokaiselle kortille pätee $\min(a_i, b_i) \le 100$.
Syöte
Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $t$ ($1 \le t \le 10^4$). Seuraavaksi annetaan testitapausten kuvaukset.
Jokainen testitapaus alkaa rivillä, joka sisältää kaksi kokonaislukua $n$ ja $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): korttien kokonaismäärän ja yhdellä pelauksella valittavien korttien lukumäärän.
Jokainen seuraavista $n$ rivistä sisältää kaksi kokonaislukua $a_i$ ja $b_i$ ($1 \le a_i, b_i \le 10^9$), jotka kuvaavat kortin arvoja. Jokaiselle kortille pätee $\min(a_i, b_i) \le 100$.
Korttien kokonaismäärä kaikissa testitapauksissa yhteensä ei ylitä arvoa $10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi kokonaisluku: suurin mahdollinen pistemäärä, joka voidaan saavuttaa valitsemalla täsmälleen $k$ korttia.
Esimerkit
Syöte 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Tuloste 1
225
Syöte 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Tuloste 2
400
Huomautus
Ensimmäisessä testitapauksessa käytämme kaikki kortit. Pistemäärä on $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Toisessa testitapauksessa meidän on jätettävä yksi kortti pois. Kortit $[2, 3, 4, 5, 6]$ sisältävän joukon arvo on $400$.
Hauska fakta: Oikeassa Balatro-pelissä kortin $a_i$ perustuu sen pokeri-arvoon, ja $b_i$ voi olla $0$, $4$ tai $20$ ($20$ esiintyy $20\%$ todennäköisyydellä). Lisäksi pelissä on satoja bonuskortteja ja sääntöjä, jotka vaikuttavat siihen, miten lukujen $a$ ja $b$ summat lasketaan.