Universal Cup Judging System

Universal Cup

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

Do we really have to explain the rules of Balatro? Just play it yourself. And remember to stop before the next contest.

For those unfamiliar with the rules: you have $n$ cards in your hand. Each card has two associated values: $a_i$ and $b_i$. You can select any subset $S$ of exactly $k$ cards and play them together to obtain a score calculated as:

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

Your task is to determine the maximum possible score you can achieve in a single play using exactly $k$ cards.

It is additionally known that the deck is balanced, meaning no card has both $a_i$ and $b_i$ simultaneously too high. Specifically, for every card, $\min(a_i, b_i) \le 100$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case begins with a line containing two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): the total number of cards and the number of cards to select for a single play.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$), representing the values of a card. For every card, $\min(a_i, b_i) \le 100$.

The total number of cards across all test cases does not exceed $10^5$.

Output

For each test case, print a single integer: the maximum possible score that can be obtained by selecting exactly $k$ cards.

Examples

Input 1

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

Output 1

225

Input 2

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

Output 2

400

Note

In the first test case, we use all the cards. The score is $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.

In the second test case, we have to drop one card. The set with cards $[2, 3, 4, 5, 6]$ has the value $400$.

Fun fact: In the real Balatro game, $a_i$ of a card is based on it's poker value, and $b_i$ can be $0$, $4$, or $20$ ($20$ can happen with a $20\%$ chance). Also, there are hundreds of bonus cards and rules that influence how the sums of $a$ and $b$ are calculated.

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.