eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шкільний бал

Шкільний бал

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Під час проведення шкільного балу планується запустити 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
Джерело Житомирська ХХVIII обласна олімпіада з інформатики