import java.io.*;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
StringTokenizer st = new StringTokenizer(br.readLine());
int maxWeight = Integer.parseInt(st.nextToken());
int numItemTypes = Integer.parseInt(st.nextToken());
int[] maxVal = new int[maxWeight + 1];
int[] itemValue = new int[numItemTypes];
int[] itemWeight = new int[numItemTypes];
int[] itemCount = new int[numItemTypes];
for (int i = 0; i < numItemTypes; i++) {
st = new StringTokenizer(br.readLine());
int value = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
itemValue[i] = value;
itemWeight[i] = weight;
itemCount[i] = count;
}
int ret = 0;
for (int i = 1; i <= (int) Math.pow(2, numItemTypes); i++) {
int bit = i;
int value = 0;
int totalWeight = 0;
for (int j = 0; j < numItemTypes; j++) {
if ((bit & 1) == 1) {
value += itemValue[j];
totalWeight += itemWeight[j];
}
bit >>= 1;
if (bit == 0) {
break;
}
}
if (totalWeight <= maxWeight)
ret = Math.max(ret, value);
}
pw.println(ret);
br.close();
pw.close();
}
}
