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]);
    }
}
 

aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CmltcG9ydCBqYXZhLnV0aWwuU2Nhbm5lcjsKCnB1YmxpYyBjbGFzcyBNYWluIHsKICAgIC8vIER5bmFtaWMgcHJvZ3JhbW1pbmcgc29sdXRpb24gYmFzZWQgb24gdGhlIGZvbGxvd2luZyByZWxhdGlvbjoKICAgIC8vIE9wdGltYWwgc29sdXRpb24gZm9yIE4gc3R1ZGVudHMgYW5kIE0gYmFsbHMgaXM6IFggYmFsbHMgZ2l2ZW4gdG8gTnRoIHN0dWRlbnQKICAgIC8vIGNvbWJpbmVkIHdpdGggb3B0aW1hbCBzb2x1dGlvbiBmb3IgTi0xIHN0dWRlbnRzIGFuZCBNLVggYmFsbHMKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgIAlTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKICAgICAgICBpbnQgbSA9IGluLm5leHRJbnQoKTsKICAgICAgICBpbnQgbiA9IGluLm5leHRJbnQoKTsKICAgICAgICBpbnRbXSBhID0gbmV3IGludFtuXTsKICAgICAgICBpbnRbXSBiID0gbmV3IGludFtuXTsKICAgICAgICBpbnRbXSBjID0gbmV3IGludFtuXTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgCWFbaV0gPSBpbi5uZXh0SW50KCk7CiAgICAgICAgCWJbaV0gPSBpbi5uZXh0SW50KCk7CiAgICAgICAgCWNbaV0gPSBpbi5uZXh0SW50KCk7CiAgICAgICAgfQoKCiAgICAgICAgaW50W10gY3VycmVudENvbHVtbiA9IG5ldyBpbnRbbSsxXTsKICAgICAgICBpbnRbXSBuZXh0Q29sdW1uID0gbmV3IGludFttKzFdOwogICAgICAgIEFycmF5cy5maWxsKG5leHRDb2x1bW4sIEludGVnZXIuTUFYX1ZBTFVFKTsKCiAgICAgICAgLy8gRmlyc3QgY29sdW1uCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gbTsgaSsrKSB7CiAgICAgICAgICAgIGN1cnJlbnRDb2x1bW5baV0gPSBhWzBdKmkgKyBjWzBdKigoaS0xKS9iWzBdKTsKICAgICAgICB9CgogICAgICAgIC8vIER5bmFtaWMgcHJvZ3JhbW1pbmcKICAgICAgICAvLyBDb2x1bW5zIG9mIERQIHRhYmxlCiAgICAgICAgZm9yKGludCBzdHVkPTE7IHN0dWQgPCBuOyBzdHVkKyspIHsKICAgICAgICAgICAgLy8gQ2VsbHMgb2YgdGhlIGNvbHVtbgogICAgICAgICAgICBmb3IgKGludCBiYWxsID0gMDsgYmFsbCA8PSBtOyBiYWxsKyspIHsKICAgICAgICAgICAgICAgIC8vIFggaXMgdGhlIG51bWJlciBvZiBiYWxscyBnaXZlbiB0byB0aGUgbmV3IHN0dWRlbnQKICAgICAgICAgICAgICAgIGZvciAoaW50IHggPSAwOyB4IDw9IGJhbGw7IHgrKykgewogICAgICAgICAgICAgICAgICAgIGludCB0aW1lU3R1ZCA9IGFbc3R1ZF0qeCArIGNbc3R1ZF0qKCh4LTEpL2Jbc3R1ZF0pOwogICAgICAgICAgICAgICAgICAgIGludCB0aW1lT3RoZXJzID0gY3VycmVudENvbHVtbltiYWxsIC0geF07CiAgICAgICAgICAgICAgICAgICAgbmV4dENvbHVtbltiYWxsXSA9IE1hdGgubWluKG5leHRDb2x1bW5bYmFsbF0sIE1hdGgubWF4KHRpbWVTdHVkLCB0aW1lT3RoZXJzKSk7CiAgICAgICAgICAgICAgICAgICAgLy8gU2hvcnRjdXQ6IGlmIGN1cnJlbnQgc3R1ZGVudCBpcyB0aGUgYm90dGxlbmVjaywgaXQgZG9lc24ndCBtYWtlIHNlbnNlIHRvIGdpdmUgaGltIG1vcmUgYmFsbHMKICAgICAgICAgICAgICAgICAgICBpZih0aW1lU3R1ZCA+IHRpbWVPdGhlcnMpIHsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIC8vIFByb2NlZWQgdG8gbmV4dCBjb2x1bW4KICAgICAgICAgICAgaW50W10gdG1wID0gY3VycmVudENvbHVtbjsKICAgICAgICAgICAgY3VycmVudENvbHVtbiA9IG5leHRDb2x1bW47CiAgICAgICAgICAgIG5leHRDb2x1bW4gPSB0bXA7CiAgICAgICAgICAgIEFycmF5cy5maWxsKG5leHRDb2x1bW4sIEludGVnZXIuTUFYX1ZBTFVFKTsKICAgICAgICB9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihjdXJyZW50Q29sdW1uW21dKTsKICAgIH0KfQo=

MTIzIDEwMAoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwozIDEwIDMKMiA0IDMKMSAyIDMKMyAxMCAzCjIgNCAzCjEgMiAzCjMgMTAgMwoyIDQgMwoxIDIgMwo=

123 100
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3
3 10 3
2 4 3
1 2 3