Universal Cup Judging System

Universal Cup

时间限制: 4.0 s 内存限制: 256 MB 总分: 100 可 Hack ✓
统计

Balatro のルールを本当に説明する必要がありますか? 自分でプレイしてみてください。ただし、次のコンテストが始まる前にはちゃんとやめるのを忘れないように。

ルールを知らない人のために説明すると、あなたは手札に $n$ 枚のカードを持っています。各カードには $a_i$ と $b_i$ という 2 つの値が割り当てられています。ちょうど $k$ 枚のカードからなる任意の部分集合 $S$ を選んで同時にプレイすると、次のように計算されるスコアを獲得できます:

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

あなたの仕事は、ちょうど $k$ 枚のカードを使った 1 回のプレイで達成できる最大スコアを求めることです。

さらに、山札はバランスが取れていることが分かっています。つまり、$a_i$ と $b_i$ の両方が同時に大きすぎるカードは存在しません。具体的には、すべてのカードについて $\min(a_i, b_i) \le 100$ が成り立ちます。

入力

各テストは複数のテストケースを含みます。1 行目にはテストケースの個数 $t$ ($1 \le t \le 10^4$) が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には 2 つの整数 $n$ と $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$) が与えられます。これらはカードの総数と 1 回のプレイで選ぶカードの枚数を表します。

続く $n$ 行にはそれぞれ、カードの値を表す 2 つの整数 $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

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 番目のテストケースでは、カードを 1 枚外す必要があります。カード $[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.