唔通我哋真係要解釋《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$ 嘅總和點樣計算。