¿De verdad tenemos que explicar las reglas de Balatro? Juégalo tú mismo. Y recuerda parar antes del próximo concurso.
Para quienes no estén familiarizados con las reglas: tienes $n$ cartas en la mano. Cada carta tiene dos valores asociados: $a_i$ y $b_i$. Puedes seleccionar cualquier subconjunto $S$ de exactamente $k$ cartas y jugarlas juntas para obtener una puntuación calculada como:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Tu tarea es determinar la máxima puntuación posible que puedes lograr en una sola jugada utilizando exactamente $k$ cartas.
Además, se sabe que la baraja está equilibrada, lo que significa que ninguna carta tiene simultáneamente $a_i$ y $b_i$ demasiado altos. Específicamente, para cada carta, $\min(a_i, b_i) \le 100$.
Entrada
Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^4$). A continuación sigue la descripción de los casos de prueba.
Cada caso de prueba comienza con una línea que contiene dos enteros $n$ y $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): el número total de cartas y el número de cartas a seleccionar para una sola jugada.
Cada una de las siguientes $n$ líneas contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i, b_i \le 10^9$), que representan los valores de una carta. Para cada carta, $\min(a_i, b_i) \le 100$.
El número total de cartas en todos los casos de prueba no supera $10^5$.
Salida
Para cada caso de prueba, imprime un único entero: la máxima puntuación posible que se puede obtener seleccionando exactamente $k$ cartas.
Ejemplos
Entrada 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Salida 1
225
Entrada 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Salida 2
400
Nota
En el primer caso de prueba, usamos todas las cartas. La puntuación es $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
En el segundo caso de prueba, tenemos que descartar una carta. El conjunto con las cartas $[2, 3, 4, 5, 6]$ tiene el valor $400$.
Dato curioso: En el juego real Balatro, el valor $a_i$ de una carta se basa en su valor de póker, y $b_i$ puede ser $0$, $4$ o $20$ ($20$ puede ocurrir con un $20\%$ de probabilidad). Además, hay cientos de cartas de bonificación y reglas que influyen en cómo se calculan las sumas de $a$ y $b$.