Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

Невже нам справді потрібно пояснювати правила Balatro? Просто зіграйте самі. І не забудьте зупинитися до початку наступного змагання.

Для тих, хто не знайомий із правилами: у вас на руках є $n$ карт. Кожній карті відповідають два значення: $a_i$ та $b_i$. Ви можете вибрати будь-яку підмножину $S$ із рівно $k$ карт і зіграти їх разом, отримавши кількість очок, що обчислюється як:

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

Ваше завдання — визначити максимально можливу кількість очок, яку можна отримати за один хід, використавши рівно $k$ карт.

Додатково відомо, що колода є збалансованою, тобто жодна карта не має одночасно занадто великих значень $a_i$ та $b_i$. Зокрема, для кожної карти виконується $\min(a_i, b_i) \le 100$.

Вхідні дані

Кожен тест містить кілька наборів вхідних даних. Перший рядок містить кількість наборів вхідних даних $t$ ($1 \le t \le 10^4$). Далі йде опис наборів вхідних даних.

Кожен набір вхідних даних починається з рядка, що містить два цілі числа $n$ і $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): загальну кількість карт і кількість карт, які потрібно вибрати для одного ходу.

Кожен із наступних $n$ рядків містить два цілі числа $a_i$ та $b_i$ ($1 \le a_i, b_i \le 10^9$), що позначають параметри карти. Для кожної карти виконується $\min(a_i, b_i) \le 100$.

Загальна кількість карт у всіх наборах вхідних даних не перевищує $10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число: максимально можливу кількість очок, яку можна отримати, вибравши рівно $k$ карт.

Приклади

Вхідні дані 1

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

Вихідні дані 1

225

Вхідні дані 2

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

Вихідні дані 2

400

Примітка

У першому наборі вхідних даних ми використовуємо всі карти. Кількість очок дорівнює $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.

У другому наборі вхідних даних потрібно відкинути одну карту. Набір із карт $[2, 3, 4, 5, 6]$ дає значення $400$.

Цікавий факт: у справжній грі Balatro значення $a_i$ карти базується на її покерному номіналі, а $b_i$ може дорівнювати $0$, $4$ або $20$ ($20$ випадає з імовірністю $20\%$). Крім того, існують сотні бонусних карт і правил, які впливають на те, як обчислюються суми $a$ та $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.