During the school ball, it is planned to launch identical balloons. senior students, each with different stamina and endurance, have volunteered to fill them with air. The -th participant can fill one balloon in a_i minutes. Each time after inflating b_i balloons, the participant takes a break lasting c_i minutes (i = 1 \ldots n).
Determine the minimum time (in minutes) required to inflate all balloons, assuming all participants work optimally.
The first line contains the numbers and (1 \le m \le 1000, 1 \le n \le 100). The following lines each contain three integers: a_i, b_i, and c_i respectively (1 \le a_i, b_i, c_i \le 100, i = 1 \ldots n).
Output the minimum time in minutes sufficient to inflate all the balloons.
Example 1