האם אנחנו באמת צריכים להסביר את החוקים של 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$.