Dobbiamo davvero spiegare le regole di Balatro? Giocaci tu stesso. E ricordati di smettere prima della prossima gara.
Per chi non conoscesse le regole: hai $n$ carte in mano. Ogni carta ha due valori associati: $a_i$ e $b_i$. Puoi selezionare qualsiasi sottoinsieme $S$ di esattamente $k$ carte e giocarle insieme per ottenere un punteggio calcolato come:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Il tuo compito è determinare il punteggio massimo possibile che puoi ottenere in una singola giocata utilizzando esattamente $k$ carte.
È inoltre noto che il mazzo è bilanciato, il che significa che nessuna carta ha contemporaneamente $a_i$ e $b_i$ troppo alti. Nello specifico, per ogni carta vale $\min(a_i, b_i) \le 100$.
Input
Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test $t$ ($1 \le t \le 10^4$). Segue la descrizione dei casi di test.
Ogni caso di test inizia con una riga contenente due interi $n$ e $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): il numero totale di carte e il numero di carte da selezionare per una singola giocata.
Ciascuna delle successive $n$ righe contiene due interi $a_i$ e $b_i$ ($1 \le a_i, b_i \le 10^9$), che rappresentano i valori di una carta. Per ogni carta vale $\min(a_i, b_i) \le 100$.
Il numero totale di carte in tutti i casi di test non supera $10^5$.
Output
Per ogni caso di test, stampa un singolo intero: il punteggio massimo possibile che può essere ottenuto selezionando esattamente $k$ carte.
Esempi
Input 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Output 1
225
Input 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Output 2
400
Note
Nel primo caso di test usiamo tutte le carte. Il punteggio è $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
Nel secondo caso di test dobbiamo scartare una carta. L'insieme con le carte $[2, 3, 4, 5, 6]$ ha valore $400$.
Curiosità: Nel vero gioco Balatro, il valore $a_i$ di una carta si basa sul suo valore di poker, mentre $b_i$ può essere $0$, $4$ oppure $20$ ($20$ può verificarsi con una probabilità del $20\%$). Inoltre, ci sono centinaia di carte bonus e regole che influenzano il modo in cui vengono calcolate le somme di $a$ e $b$.