School Ball#7227

School Ball

1 second
64 megabytes
Easy

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.

Input

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

Output the minimum time in minutes sufficient to inflate all the balloons.

Examples

Example 1

Loading
Loading