Universal Cup Judging System

Universal Cup

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

Chúng tôi có thực sự phải giải thích luật chơi của Balatro không? Hãy tự mình chơi thử đi. Và nhớ dừng lại trước kỳ thi tiếp theo nhé.

Dành cho những ai chưa quen với luật chơi: bạn có $n$ lá bài trên tay. Mỗi lá bài có hai giá trị đi kèm: $a_i$ và $b_i$. Bạn có thể chọn một tập con $S$ bất kỳ gồm đúng $k$ lá bài và đánh chúng cùng nhau để nhận được số điểm tính theo công thức:

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

Nhiệm vụ của bạn là xác định số điểm tối đa có thể đạt được trong một lượt đánh sử dụng đúng $k$ lá bài.

Ngoài ra, biết rằng bộ bài cân bằng, nghĩa là không có lá bài nào có cả $a_i$ và $b_i$ đồng thời quá cao. Cụ thể, với mọi lá bài, $\min(a_i, b_i) \le 100$.

Dữ liệu vào

Mỗi test chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 10^4$). Mô tả của các bộ dữ liệu theo sau.

Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên $n$ và $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): tổng số lá bài và số lượng lá bài cần chọn cho một lượt đánh.

Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i, b_i \le 10^9$), biểu thị các giá trị của một lá bài. Với mọi lá bài, $\min(a_i, b_i) \le 100$.

Tổng số lá bài trong tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số điểm tối đa có thể đạt được bằng cách chọn đúng $k$ lá bài.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

225

Dữ liệu vào 2

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

Dữ liệu ra 2

400

Ghi chú

Trong bộ dữ liệu đầu tiên, chúng ta sử dụng tất cả các lá bài. Số điểm là $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.

Trong bộ dữ liệu thứ hai, chúng ta phải bỏ đi một lá bài. Tập hợp gồm các lá bài $[2, 3, 4, 5, 6]$ có giá trị là $400$.

Sự thật thú vị: Trong trò chơi Balatro thực tế, $a_i$ của một lá bài dựa trên giá trị poker của nó, còn $b_i$ có thể là $0$, $4$, hoặc $20$ ($20$ có thể xảy ra với xác suất $20\%$). Ngoài ra, có hàng trăm lá bài thưởng và quy tắc ảnh hưởng đến cách tính tổng của $a$ và $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.