Codeforces Round 657 (Div. 2) |
---|
Закончено |
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из ровно $$$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$$$.
Название |
---|