Школьный бал

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

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

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

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

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

Примеры