import java.util.Arrays;
import java.util.Scanner;

public class Main {
    // Dynamic programming solution based on the following relation:
    // Optimal solution for N students and M balls is: X balls given to Nth student
    // combined with optimal solution for N-1 students and M-X balls
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for(int i = 0; i < n; i++) {
        	a[i] = in.nextInt();
        	b[i] = in.nextInt();
        	c[i] = in.nextInt();
        }


        int[] currentColumn = new int[m+1];
        int[] nextColumn = new int[m+1];
        Arrays.fill(nextColumn, Integer.MAX_VALUE);

        // First column
        for (int i = 0; i <= m; i++) {
            currentColumn[i] = a[0]*i + c[0]*((i-1)/b[0]);
        }

        // Dynamic programming
        // Columns of DP table
        for(int stud=1; stud < n; stud++) {
            // Cells of the column
            for (int ball = 0; ball <= m; ball++) {
                // X is the number of balls given to the new student
                for (int x = 0; x <= ball; x++) {
                    int timeStud = a[stud]*x + c[stud]*((x-1)/b[stud]);
                    int timeOthers = currentColumn[ball - x];
                    nextColumn[ball] = Math.min(nextColumn[ball], Math.max(timeStud, timeOthers));
                    // Shortcut: if current student is the bottleneck, it doesn't make sense to give him more balls
                    if(timeStud > timeOthers) {
                        break;
                    }
                }
            }
            // Proceed to next column
            int[] tmp = currentColumn;
            currentColumn = nextColumn;
            nextColumn = tmp;
            Arrays.fill(nextColumn, Integer.MAX_VALUE);
        }

        System.out.println(currentColumn[m]);
    }
}