e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Школьный бал

Школьный бал

Во время проведения школьного бала планируется запустить m одинаковых воздушных шариков. Наполнить их воздухом согласились n старшеклассников с различной силой духа и выносливостью. Известно, что i-ый участник процесса наполняет один шарик воздухом за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci минут (i = 1..n). Нужно узнать за какое минимальное время (в минутах) будут надуты все шарики при оптимальной работе всех участников.

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

В первой строке находятся числа m и n (1 m 1000, 1n 100). В следующих n строках по три целых числа - ai, bi, ci соответственно (1 ai, bi, ci100, i = 1..n)

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

Время в минутах, достаточное для надувания всех шариков.

Time limit 1 second
Memory limit 64 MiB
Input example #1
10 3
1 2 3
3 10 3
2 4 3
Output example #1
8
Source Житомирская ХХVIII обласная олимпиада по информатике