Problems
Школьный бал
Школьный бал
Во время проведения школьного бала планируется запустить m одинаковых воздушных шариков. Наполнить их воздухом согласились n старшеклассников с различной силой духа и выносливостью. Известно, что i-ый участник процесса наполняет один шарик воздухом за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci минут (i = 1..n). Нужно узнать за какое минимальное время (в минутах) будут надуты все шарики при оптимальной работе всех участников.
Входные данные
В первой строке находятся числа m и n (1 ≤ m ≤ 1000, 1 ≤ n ≤ 100). В следующих n строках по три целых числа - ai, bi, ci соответственно (1 ≤ ai, bi, ci ≤ 100, i = 1..n)
Выходные данные
Время в минутах, достаточное для надувания всех шариков.
Input example #1
10 3 1 2 3 3 10 3 2 4 3
Output example #1
8