Do we really have to explain the rules of Balatro? Just play it yourself. And remember to stop before the next contest.
For those unfamiliar with the rules: you have $n$ cards in your hand. Each card has two associated values: $a_i$ and $b_i$. You can select any subset $S$ of exactly $k$ cards and play them together to obtain a score calculated as:
$$\left(\sum_{i \in S} a_i\right) \cdot \left(\sum_{i \in S} b_i\right)$$
Your task is to determine the maximum possible score you can achieve in a single play using exactly $k$ cards.
It is additionally known that the deck is balanced, meaning no card has both $a_i$ and $b_i$ simultaneously too high. Specifically, for every card, $\min(a_i, b_i) \le 100$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
Each test case begins with a line containing two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le \min(n, 5)$): the total number of cards and the number of cards to select for a single play.
Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$), representing the values of a card. For every card, $\min(a_i, b_i) \le 100$.
The total number of cards across all test cases does not exceed $10^5$.
Output
For each test case, print a single integer: the maximum possible score that can be obtained by selecting exactly $k$ cards.
Examples
Input 1
1 5 5 1 1 2 2 3 3 4 4 5 5
Output 1
225
Input 2
1 6 5 1 1 2 6 3 5 4 4 5 3 6 2
Output 2
400
Note
In the first test case, we use all the cards. The score is $(1 + 2 + 3 + 4 + 5) \cdot (1 + 2 + 3 + 4 + 5) = 15^2 = 225$.
In the second test case, we have to drop one card. The set with cards $[2, 3, 4, 5, 6]$ has the value $400$.
Fun fact: In the real Balatro game, $a_i$ of a card is based on it's poker value, and $b_i$ can be $0$, $4$, or $20$ ($20$ can happen with a $20\%$ chance). Also, there are hundreds of bonus cards and rules that influence how the sums of $a$ and $b$ are calculated.