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$ қосындыларының қалай есептелетініне әсер ететін жүздеген бонустық карталар мен ережелер бар.