- Описание
- Отправленные решения
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 чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
1 2
2 1 1
1 1 2
1
0 1
Пример 2
2 2
1 1 1
1 1 1
1
1 1