เราต้องอธิบายกติกาของเกม Balatro จริงๆ หรือ? ลองไปเล่นด้วยตัวเองเถอะ และอย่าลืมหยุดเล่นก่อนการแข่งขันครั้งต่อไปด้วยล่ะ
สำหรับผู้ที่ไม่คุ้นเคยกับกติกา: คุณมีไพ่ $n$ ใบอยู่ในมือ ไพ่แต่ละใบมีค่าที่เกี่ยวข้องสองค่าคือ $a_i$ และ $b_i$ คุณสามารถเลือกสับเซต $S$ ใดๆ ที่มีไพ่จำนวน $k$ ใบพอดี แล้วเล่นไพ่เหล่านั้นพร้อมกันเพื่อให้ได้คะแนนซึ่งคำนวณดังนี้:
$$\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$