Devons-nous vraiment expliquer les règles de Balatro ? Jouez-y vous-même. Et n'oubliez pas de vous arrêter avant le prochain concours.
Pour ceux qui ne connaissent pas les règles : vous avez $n$ cartes en main. Chaque carte possède deux valeurs associées : $a_i$ et $b_i$. Vous pouvez sélectionner n'importe quel sous-ensemble $S$ d'exactement $k$ cartes et les jouer ensemble pour obtenir un score calculé comme suit :
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Votre tâche consiste à déterminer le score maximum possible que vous pouvez atteindre en un seul coup en utilisant exactement $k$ cartes.
On sait de plus que le paquet est équilibré, ce qui signifie qu'aucune carte n'a simultanément $a_i$ et $b_i$ trop élevés. Plus précisément, pour chaque carte, $\min(a_i, b_i) \le 100$.
Entrée
Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 10^4$). La description des cas de test suit.
Chaque cas de test commence par une ligne contenant deux entiers $n$ et $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$) : le nombre total de cartes et le nombre de cartes à sélectionner pour un seul coup.
Chacune des $n$ lignes suivantes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i, b_i \le 10^9$), représentant les valeurs d'une carte. Pour chaque carte, $\min(a_i, b_i) \le 100$.
Le nombre total de cartes sur l'ensemble des cas de test ne dépasse pas $10^5$.
Sortie
Pour chaque cas de test, affichez un seul entier : le score maximum possible pouvant être obtenu en sélectionnant exactement $k$ cartes.
Exemples
Entrée 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Sortie 1
225
Entrée 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Sortie 2
400
Remarque
Dans le premier cas de test, nous utilisons toutes les cartes. Le score est $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Dans le deuxième cas de test, nous devons écarter une carte. L'ensemble contenant les cartes $[2, 3, 4, 5, 6]$ donne la valeur $400$.
Anecdote : Dans le vrai jeu Balatro, la valeur $a_i$ d'une carte dépend de sa valeur au poker, et $b_i$ peut valoir $0$, $4$ ou $20$ ($20$ pouvant survenir avec une probabilité de $20\%$). De plus, il existe des centaines de cartes bonus et de règles qui influencent la manière dont les sommes des $a$ et des $b$ sont calculées.