C. Выбор цветов для букета
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из ровно $$$n$$$ цветов.

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов $$$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$$$) — требуемое количество цветов в букете и количество доступных видов цветов.

Каждая из следующих $$$m$$$ строк описывает вид цветов и содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — увеличение счастья от первого цветка $$$i$$$-го вида и увеличение счастья от каждого последующего цветка этого вида.

Наборы разделены одной пустой строкой.

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$100\,000$$$.

Выходные данные

Для каждого набора входных данных в единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из $$$n$$$ цветов.

Пример
Входные данные
2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1
Выходные данные
14
16
Примечание

В первом примере если взять 1 цветок первого типа и 3 цветка второго типа, то итоговое увеличение счастья от букета будет равно $$$5 + (1 + 2 \cdot 4) = 14$$$.

В втором примере если взять 2 цветка первого типа, 2 цветка второго типа и 1 цветок третьего типа, то итоговое увеличение счастья от букета будет равно $$$(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$$$.