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

Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за $T_i$ минут, однако каждый раз после надувания $Z_i$ шариков устает и отдыхает $Y_i$ минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

В первой строке входных данных задаются числа M и N (0 $\le$ M $\le$  15000, 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).

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