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$ の和の計算方法に影響を与える何百ものボーナスカードやルールが存在します。