题目描述

有 $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)$

每组数据后有一个空行。保证所有测试用例的 $m$ 值总和不超过 $10^5$ 。

输出格式

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

2
4 3
5 0
1 4
2 2
5 3
5 2
4 2
3 1

14
16

说明/提示

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