Universal Cup Judging System

Universal Cup

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

Czy naprawdę musimy tłumaczyć zasady gry Balatro? Po prostu sam w nią zagraj. I pamiętaj, żeby przestać przed następnymi zawodami.

Dla osób niezaznajomionych z zasadami: masz w ręku $n$ kart. Każda karta ma dwie przypisane wartości: $a_i$ oraz $b_i$. Możesz wybrać dowolny podzbiór $S$ składający się z dokładnie $k$ kart i zagrać je razem, uzyskując wynik obliczany jako:

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

Twoim zadaniem jest wyznaczenie maksymalnego możliwego wyniku, jaki możesz osiągnąć w jednym zagraniu, używając dokładnie $k$ kart.

Dodatkowo wiadomo, że talia jest zbalansowana, co oznacza, że żadna karta nie ma jednocześnie zbyt dużych wartości $a_i$ oraz $b_i$. Dokładniej, dla każdej karty zachodzi $\min(a_i, b_i) \le 100$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^4$). Następnie podane są opisy kolejnych przypadków testowych.

Każdy przypadek testowy zaczyna się od wiersza zawierającego dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): łączną liczbę kart oraz liczbę kart do wybrania w jednym zagraniu.

Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i, b_i \le 10^9$), oznaczające wartości karty. Dla każdej karty zachodzi $\min(a_i, b_i) \le 100$.

Łączna liczba kart we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: maksymalny możliwy wynik, jaki można uzyskać, wybierając dokładnie $k$ kart.

Przykład

Wejście 1

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

Wyjście 1

225

Wejście 2

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

Wyjście 2

400

Uwagi

W pierwszym przypadku testowym używamy wszystkich kart. Wynik wynosi $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.

W drugim przypadku testowym musimy odrzucić jedną kartę. Zbiór kart $[2, 3, 4, 5, 6]$ daje wartość $400$.

Ciekawostka: W prawdziwej grze Balatro wartość $a_i$ karty zależy od jej wartości pokerowej, a $b_i$ może wynosić $0$, $4$ lub $20$ ($20$ wypada z prawdopodobieństwem $20\%$). Ponadto istnieją setki kart bonusowych i zasad wpływających na sposób obliczania sum wartości $a$ oraz $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.