eolymp
bolt
Try our new interface for solving problems
Məsələlər

Школьный бал

Школьный бал

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Во время проведения школьного бала планируется запустить m одинаковых воздушных шариков. Наполнить их воздухом согласились n старшеклассников с различной силой духа и выносливостью. Известно, что i-ый участник процесса наполняет один шарик воздухом за a_i минут, причем каждый раз после надувания b_i шариков отдыхает и переводит дух c_i минут (i = 1..n). Нужно узнать за какое минимальное время (в минутах) будут надуты все шарики при оптимальной работе всех участников.

Giriş verilənləri

В первой строке находятся числа m и n (1 m 1000, 1n 100). В следующих n строках по три целых числа - a_i, b_i, c_i соответственно (1 a_i, b_i, c_i100, i = 1..n)

Çıxış verilənləri

Время в минутах, достаточное для надувания всех шариков.

Nümunə

Giriş verilənləri #1
10 3
1 2 3
3 10 3
2 4 3
Çıxış verilənləri #1
8
Mənbə Житомирская ХХVIII обласная олимпиада по информатике