弗拉基米尔想给他的妻子准备一份礼物:他们有周年纪念日!他决定给她买$$$n$$$的花。
Vladimir去了一家花店,他惊讶地发现那里出售的鲜花有$$$m$$$种,而且每种花都无限量供应。弗拉基米尔想选择鲜花来最大限度地提高妻子的幸福感。他知道,在收到第 $$$i$$$ 类型的第一朵花后,妻子的幸福感增加了 $$$a_i$$$,并且在连续收到这种类型的每一朵花后,她的幸福感增加了 $$$b_i$$$。也就是说,如果在所选的花中存在 $$$x_i > 0$$$ 类型为 $$$i$$$ 的花,则他的妻子将获得 $$$a_i + (x_i - 1) \cdot b_i$$$ 额外的幸福(如果没有 $$$i$$$ 类型的花,则她不会获得该特定类型的任何东西)。
请帮助弗拉基米尔正确选择 $$$n$$$ 鲜花,以最大限度地提高他妻子的幸福感。
输入
第一行包含唯一的整数$$$t$$$ ($$$1 \leq t \leq 10\,000$$$),测试用例的数量。接下来是测试用例的 $$$t$$$ 描述。
每个测试用例描述都以两个整数 $$$n$$$ 和 $$$m$$$ 开头($$$1 \le n \le 10^9$$$, $$$1 \le m \le 100\,000$$$),Vladimir 需要选择的花朵数量以及可用花朵的类型数量。
以下 $$$m$$$ 行描述了花的类型:每行包含整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$),表示第 $$$i$$$ 种可用的花类型。
测试用例由空行分隔。保证所有测试用例的值$$$m$$$之和不超过$$$100\,000$$$。
输出
对于每个测试用例,输出一个整数:在最佳选择 $$$n$$$ 花后,Vladimir 的妻子的最大总幸福感。
示例
输入 #1
2 4 3 5 0 1 4 2 2 5 3 5 2 4 2 3 1
输出 #1
14 16
注意
在第一个示例中,Vladimir 可以摘 1 朵第一类型的花和 3 朵第二类型的花,在这种情况下,总幸福感等于 $$$5 + (1 + 2 \cdot 4) = 14$$$。
在第二个例子中,Vladimir 可以摘 2 朵第一类花、2 朵第二类花和 1 朵第三类花,在这种情况下,总幸福感等于 $$$(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$$$。