Анонс #195. Детский праздник

Задача: для организации детского праздника необходимо надуть M воздушных шариков. Для этого организаторы позвали N добровольцев, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут.

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

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

Входные данные: M, N - натуральные числа, где 0<=M<=1000; 1<=N<=20. 

List - список из N наборов, каждый набор содержит по 3 значения для Ti, Zi, Yi соот-но, где 1<=Ti, Yi<=100; 1<=Zi<=1000.

Вывод: минимально возможное время, за которое будут надуты все шарики.

Пример:

1. M = 10; N = 3;

List = { (T: 1, Z: 2, Y: 3), 

(T: 3, Z: 10, Y: 3), 

(T: 2, Z: 4, Y: 3) }

Answer = 8;

2. M = 3; N = 2;

List = { (T: 2, Z: 2, Y: 5), 

(T: 1, Z: 1, Y: 10) }

Answer = 4;