|
Воздушные шарики
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
В детском саду «Буратино» воспитатели решили организовать праздник для детей, для чего запланировали надуть M воздушных шариков. С этой целью они пригласили N помощников, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут. Теперь воспитатели желают узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. При этом, если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха.
Входные данные
В первой строке входного файла INPUT.TXT находятся числа M и N (0 ≤ M ≤ 1000, 1 ≤ N ≤ 20). Следующие N строк содержат по три целых числа – Ti, Zi и Yi соответственно (1 ≤ Ti,Yi ≤ 100, 1 ≤ Zi ≤ 1000).
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число T – время, за которое будут надуты все шарики. Во второй строке выведите N чисел – сколько шариков надует каждый из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 3
1 2 3
3 10 3
2 4 3 | 8
4 2 4 |
| 2 | 1 3
1 1 100
2 1 100
3 1 100 | 1
1 0 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
