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