Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 256 MB Total points: 100 Hackable ✓
Statistics

Må vi virkelig forklare reglene i Balatro? Bare spill det selv. Og husk å stoppe før neste konkurranse.

For dem som ikke kjenner reglene: du har $n$ kort på hånden. Hvert kort har to tilhørende verdier: $a_i$ og $b_i$. Du kan velge en hvilken som helst delmengde $S$ med nøyaktig $k$ kort og spille dem sammen for å oppnå en poengsum som beregnes som:

$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$

Oppgaven din er å finne den maksimale poengsummen du kan oppnå i ett enkelt trekk ved å bruke nøyaktig $k$ kort.

Det er i tillegg kjent at kortstokken er balansert, noe som betyr at ingen kort har både $a_i$ og $b_i$ samtidig for høye. Spesifikt gjelder det for hvert kort at $\min(a_i, b_i) \le 100$.

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder antallet testtilfeller $t$ ($1 \le t \le 10^4$). Beskrivelsen av testtilfellene følger.

Hvert testtilfelle begynner med en linje som inneholder to heltall $n$ og $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): det totale antallet kort og antallet kort som skal velges for ett enkelt trekk.

Hver av de neste $n$ linjene inneholder to heltall $a_i$ og $b_i$ ($1 \le a_i, b_i \le 10^9$), som representerer verdiene til et kort. For hvert kort gjelder $\min(a_i, b_i) \le 100$.

Det totale antallet kort over alle testtilfeller overstiger ikke $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut ett enkelt heltall: den maksimale poengsummen som kan oppnås ved å velge nøyaktig $k$ kort.

Eksempler

Inndata 1

1
5 5
1 1
2 2
3 3
4 4
5 5

Utdata 1

225

Inndata 2

1
6 5
1 1
2 6
3 5
4 4
5 3
6 2

Utdata 2

400

Forklaring

I det første testtilfellet bruker vi alle kortene. Poengsummen er $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.

I det andre testtilfellet må vi droppe ett kort. Mengden med kortene $[2, 3, 4, 5, 6]$ har verdien $400$.

Morsomt fakta: I det virkelige spillet Balatro er $a_i$ for et kort basert på poker-verdien til kortet, og $b_i$ kan være $0$, $4$ eller $20$ ($20$ kan forekomme med $20\%$ sjanse). I tillegg finnes det hundrevis av bonuskort og regler som påvirker hvordan summene av $a$ og $b$ beregnes.

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.