Universal Cup Judging System

Universal Cup

実行時間制限: 4.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓
統計

Balatro의 규칙을 정말 설명해야 할까요? 직접 플레이해 보세요. 그리고 다음 대회가 시작하기 전에 멈추는 것을 잊지 마세요.

규칙에 익숙하지 않은 분들을 위해 설명하자면: 당신의 손에는 $n$장의 카드가 있습니다. 각 카드에는 두 개의 값 $a_i$와 $b_i$가 부여되어 있습니다. 정확히 $k$장의 카드로 이루어진 부분집합 $S$를 아무거나 선택하여 함께 내면 다음과 같이 계산되는 점수를 얻습니다:

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