我们真的需要解释《小丑牌》（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$。

趣闻：在真正的《小丑牌》游戏中，一张牌的 $a_i$ 取决于它的扑克牌面值，而 $b_i$ 可以是 0、4 或 20（20 有 20% 的概率出现）。此外，还有数百张金卡（bonus cards）和规则会影响 $a$ 和 $b$ 的和的计算方式。