import java.io.*;
import java.util.*;

public class DWITE3 {
	public static void main (String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("DATA3.txt"));
		PrintWriter pw = new PrintWriter(new FileWriter("OUT3.txt"));
		
		//iterate five times
		for (int i = 0; i < 5; i ++) {
			space = Integer.parseInt(br.readLine());
			int num = Integer.parseInt(br.readLine());
			Song [] list = new Song [num];
			for (int n = 0; n < num; n ++) {
				String line = br.readLine();
				StringTokenizer st = new StringTokenizer (line, " ");
				st.nextToken();
				list[n] = new Song (Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
//				System.out.println (list[n]);
			}
			int x = bestSum (list);
			pw.println(x);
			highestRating = 0;
			ratingSum = 0;
			spaceSum = 0;
		}
		pw.close();
	}
	
	static int space;
	static int highestRating = 0;
	static int ratingSum = 0;
	static int spaceSum = 0;
	
	public static int bestSum (Song [] list) {
		int ratingSum = 0;
		int spaceSum = 0;
		recur (list, ratingSum, spaceSum);
		return highestRating;
	}
	
	public static void recur (Song [] list, int ratingSum, int spaceSum) {
		for (int i = 0; i < list.length; i ++) {
//			System.out.println (list[i]);
			int nextSpaceSum = spaceSum + list[i].space;
			int nextRatingSum = ratingSum + list[i].rating;
			if (nextSpaceSum <= space) {
				if (nextRatingSum > highestRating) {
					highestRating = nextRatingSum;
				}
				else {
					Song [] newList = new Song [list.length - 1];
					for (int j = 0; j < i; j ++) {
						newList[j] = list[j];
					}
					for (int j = i+1; j < list.length; j++) {
						newList[j-1] = list[j];
					}
					recur (newList, ratingSum+list[i].rating, spaceSum + list[i].space);
				}
			}
		}
	}
}

class Song {
	int rating;
	int space;
	public Song (int rating, int space) {
		this.rating = rating;
		this.space = space;
	}
		
	public String toString () {
		return "rating: " + rating + " memory: " + space;
	}
}