Задачі
Шкільний бал
Шкільний бал
Під час проведення шкільного балу планується запустити m однакових повітряних кульок. Наповнити їх повітрям погодилися n охочих до такої роботи старшокласників з різною силою духу і витривалістю. Відомо, що i-ий учасник процесу наповнює одну кульку повітрям за A[i] хвилин, причому кожен раз після надування B[i] кульок відпочиває і переводить дух C[i] хвилин (i=1..N). Важливо знати за який мінімальний час (у хвилинах) будуть надуті всі кульки при оптимальній роботі всіх учасників.
Вхідні дані: В першому рядку знаходяться числа M і N (1<=M<=1000, 1<=N<=100). У наступних N рядках по три цілих числа - A[i] B[i] C[i] відповідно (1<= A[i], B[i], C[i] <=100, i=1..N)
Вихідні дані:Час в хвилинах достатній для надування всіх кульок.
Приклад
Вхідні дані #1
10 3 1 2 3 3 10 3 2 4 3
Вихідні дані #1
8