هل يتعين علينا حقًا شرح قواعد لعبة 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$.