N. Детский праздник

К празднику нужно надуть $M$ воздушных шариков. Позвали $N$ помощников: $i$-й надувает шарик за $T_i$ минут, но после каждых $Z_i$ надутых шариков устаёт и отдыхает $Y_i$ минут.

Все помощники работают одновременно и независимо. Если помощник надул шарик и должен отдыхать, но шариков больше надувать не придётся, он считается закончившим сразу после надувания последнего шарика, а не после отдыха.

За какое наименьшее время будут надуты все шарики?

Первая строка содержит числа $M$ и $N$ ($0 \le M \le 10^5$, $1 \le N \le 1000$).

Следующие $N$ строк содержат по три целых числа $T_i$, $Z_i$ и $Y_i$ ($1 \le T_i, Y_i \le 100$, $1 \le Z_i \le 1000$).

Одно число — наименьшее время в минутах.