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

Неужели нам действительно нужно объяснять правила 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.