CF1379C Choosing flowers

有 $m$ 种物品，每种物品有无限个，你可以购买 $n$ 个物品。 对于第 $i$ 种物品： 第一次买时的贡献是 $a_i$ ,接下来每购买一个的贡献都是 $b_i$。即当你买了 $x_i$ 个第 $i$ 种物品时，贡献是 $a_i+b_i \times (x_i-1)$ 现在要你求出最大贡献。

第一行一个 $t (1≤t≤10^4)$，表示有 $t$ 组数据。 对于每组数据： 第一行$n$ 和 $m (1≤n≤10^9,1≤m≤10^5)$ 接下来 $m$ 行，每行两个整数$a_i$和$b_i(0≤a_i,b_i≤10^9)$ 每组数据后有一个空行。

对于每组数据，输出一行一个整数表示最大的贡献。

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 $ .