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$의 합이 계산되는 방식에 영향을 주는 수백 가지의 보너스 카드와 규칙이 있습니다.