CF1379C.Choosing flowers

Vladimir would like to prepare a present for his wife: they have an anniversary! He decided to buy her exactly $n$ flowers.

Vladimir went to a flower shop, and he was amazed to see that there are $m$ types of flowers being sold there, and there is unlimited supply of flowers of each type. Vladimir wants to choose flowers to maximize the happiness of his wife. He knows that after receiving the first flower of the $i$-th type happiness of his wife increases by $a_i$ and after receiving each consecutive flower of this type her happiness increases by $b_i$. That is, if among the chosen flowers there are $x_i \gt 0$ flowers of type $i$, his wife gets $a_i + (x_i - 1) \cdot b_i$ additional happiness (and if there are no flowers of type $i$, she gets nothing for this particular type).

Please help Vladimir to choose exactly $n$ flowers to maximize the total happiness of his wife.

弗拉基米尔想为妻子准备一份礼物：他们要庆祝结婚纪念日！他决定恰好购买 $n$ 朵花。

弗拉基米尔来到一家花店，惊讶地发现店里共出售 $m$ 种花卉，且每种花卉的供应量都是无限的。弗拉基米尔希望选择花卉，以使妻子的幸福值最大化。他了解到：妻子收到第 $i$ 种花卉的第一朵时，幸福值增加 $a_i$；之后每再收到一朵该种类的花，幸福值额外增加 $b_i$。也就是说，若所选花朵中第 $i$ 种花卉有 $x_i \gt 0$ 朵，则妻子由此获得的额外幸福值为 $a_i + (x_i - 1) \cdot b_i$（若第 $i$ 种花卉一朵也没选，则该种类带来的幸福值为 $0$）。

请帮助弗拉基米尔恰好选择 $n$ 朵花，使得妻子的总幸福值最大。

The first line contains the only integer $t$ ($1 \leq t \leq 10\,000$), the number of test cases. It is followed by $t$ descriptions of the test cases.

Each test case description starts with two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 100\,000$), the number of flowers Vladimir needs to choose and the number of types of available flowers.

The following $m$ lines describe the types of flowers: each line contains integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) for $i$-th available type of flowers.

The test cases are separated by a blank line. It is guaranteed that the sum of values $m$ among all test cases does not exceed $100\,000$.

第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。随后是 $t$ 个测试用例的描述。

每个测试用例的描述以两个整数 $n$ 和 $m$（$1 \le n \le 10^9$，$1 \le m \le 100\,000$）开始，分别表示弗拉基米尔需要选择的花朵总数以及可用的花的种类数。

接下来的 $m$ 行描述了各种花的类型：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 10^9$）。

各测试用例之间以空行分隔。保证所有测试用例中 $m$ 的总和不超过 $100\,000$。

For each test case output a single integer: the maximum total happiness of Vladimir's wife after choosing exactly $n$ flowers optimally.

对于每个测试用例，输出一个整数：弗拉基米尔的妻子在恰好选择 $n$ 朵花并进行最优选择后所能获得的最大总幸福感。

In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals $5 + (1 + 2 \cdot 4) = 14$.

In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals $(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$.

在第一个样例中，弗拉基米尔可以选取 1 朵第一类花和 3 朵第二类花，此时总幸福值为 $5 + (1 + 2 \cdot 4) = 14$。

在第二个样例中，弗拉基米尔可以选取 2 朵第一类花、2 朵第二类花和 1 朵第三类花，此时总幸福值为 $(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$。