Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из ровно \(n\) цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов \(m\) различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка \(i\)-го вида в букете его супруга становится счастливее на \(a_i\), а от каждого следующего цветка такого вида она становится счастливее на \(b_i\). То есть, если в букете \(x_i > 0\) цветов вида \(i\), то за цветы этого вида жена Володи становится счастливее на \(a_i + (x_i - 1) \cdot b_i\) (а в случае, если цветов типа \(i\) в букете не будет, счастье жены Володи из-за цветов этого типа не изменится).
Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета из \(n\) цветов, набранного из доступных в магазине цветов.
Выходные данные
Для каждого набора входных данных в единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из \(n\) цветов.
Примечание
В первом примере если взять 1 цветок первого типа и 3 цветка второго типа, то итоговое увеличение счастья от букета будет равно \(5 + (1 + 2 \cdot 4) = 14\).
В втором примере если взять 2 цветка первого типа, 2 цветка второго типа и 1 цветок третьего типа, то итоговое увеличение счастья от букета будет равно \((5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 3
5 0
1 4
2 2
5 3
5 2
4 2
3 1
|
14
16
|