我們真的有必要解釋《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$ 的總和如何計算。