• Детский праздник
  HOLIDAY

Организаторы детского праздника планируют надуть для него m воздушных шариков. С этой целью они пригласили n добровольных помощников, i-й среди которых надувает шарик за t_i минут, однако каждый раз после надувания z_i шариков устает и отдыхает y_i минут. 

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

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

Технические требования:

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на тест.

Формат входных данных:
Входной текстовый файл INPUT.TXT содержит:
- в первой строке числа m и n (0£m£1000, 0£n£20);
- ñледующие n строк содержат по три целых числа – t_i, z_i и y_i (1£t_i, y_i£100, 1£z_i£1000)

Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается в первой строке число t – время, за которое будут надуты все шарики. Во вторую строку записывается n чисел – сколько шариков надует каждый из помощников. Числа разделить пробелами. Если распределений несколько, вывести любое из них.

Пример:

INPUT.TXT
10 3
1 2 3
3 10 3
2 4 3

OUTPUT.TXT
8
4 2 4