Apakah kita benar-benar harus menjelaskan aturan Balatro? Mainkan saja sendiri. Dan ingatlah untuk berhenti sebelum kontes berikutnya.
Bagi yang belum mengenal aturannya: Anda memiliki $n$ kartu di tangan Anda. Setiap kartu memiliki dua nilai terkait: $a_i$ dan $b_i$. Anda dapat memilih himpunan bagian $S$ mana pun yang terdiri atas tepat $k$ kartu dan memainkannya bersama-sama untuk memperoleh skor yang dihitung sebagai:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Tugas Anda adalah menentukan skor maksimum yang mungkin dapat Anda capai dalam satu kali permainan menggunakan tepat $k$ kartu.
Selain itu, diketahui bahwa dek kartu tersebut seimbang, yang berarti tidak ada kartu yang memiliki nilai $a_i$ dan $b_i$ yang keduanya terlalu tinggi secara bersamaan. Secara spesifik, untuk setiap kartu, berlaku $\min(a_i, b_i) \le 100$.
Masukan
Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $t$ ($1 \le t \le 10^4$). Deskripsi dari masing-masing kasus uji menyusul.
Setiap kasus uji dimulai dengan satu baris yang berisi dua bilangan bulat $n$ dan $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): jumlah seluruh kartu dan banyaknya kartu yang harus dipilih untuk satu kali permainan.
Masing-masing dari $n$ baris berikutnya berisi dua bilangan bulat $a_i$ dan $b_i$ ($1 \le a_i, b_i \le 10^9$), yang menyatakan nilai-nilai dari sebuah kartu. Untuk setiap kartu, $\min(a_i, b_i) \le 100$.
Jumlah seluruh kartu di semua kasus uji tidak melebihi $10^5$.
Keluaran
Untuk setiap kasus uji, cetak satu bilangan bulat: skor maksimum yang mungkin diperoleh dengan memilih tepat $k$ kartu.
Contoh
Masukan 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Keluaran 1
225
Masukan 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Keluaran 2
400
Catatan
Pada kasus uji pertama, kita menggunakan semua kartu. Skornya adalah $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Pada kasus uji kedua, kita harus membuang satu kartu. Himpunan dengan kartu $[2, 3, 4, 5, 6]$ memiliki nilai $400$.
Fakta menarik: Dalam permainan Balatro yang sebenarnya, $a_i$ dari sebuah kartu didasarkan pada nilai poker-nya, dan $b_i$ dapat bernilai $0$, $4$, atau $20$ ($20$ dapat terjadi dengan peluang $20\%$). Selain itu, terdapat ratusan kartu bonus dan aturan yang memengaruhi bagaimana jumlah $a$ dan $b$ dihitung.