0
0 комментариев

Организаторы детского праздника планируют надуть для него m воздушных шариков. С этой целью они пригласили n добровольных помощников, i-й среди которых надувает шарик за ti минут, однако каждый раз после надувания zi шариков устает и отдыхает yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Входные данные
В первой строке входных данных задаются числа m и n (0≤m≤15000,1≤n≤1000). Следующие n строк содержат по три целых числа — ti, zi и yi соответственно (1≤ti,yi≤100,1≤zi≤1000).

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

Пример
входные данные
1 2
2 1 1
1 1 2

выходные данные
1
0 1

Arnfinn изменил статус на опубликованный 17.12.2022