Universal Cup Judging System

Universal Cup

Süre Sınırı: 4.0 s Bellek Sınırı: 256 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

¿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$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.