#include <fstream>
#include <string>
#include <iostream>

using namespace std;


void sort(int array[], int array1[], int size);

int main(){
    ifstream in("DATA4.txt");
    ofstream out("OUT4.txt");
    for(int a=0; a< 5; a++){
    int max;
    in >> max;

    int size;
    in >> size;

    int inputSize[size];
    int inputUtil[size];
    for(int i = 0; i < size; i++){
        in >> inputSize[i];
        in >> inputUtil[i];
    }

    sort(inputSize, inputUtil, size);
    int counter = 0;
    int maxUtil = 0;
    for(int x = 0; x < size; x++){
        int currentSize = 0;
        int holderUtil = 0;
        for(int i = counter; i < size; i++){
            currentSize += inputSize[i];
            if(currentSize > max) break;
            holderUtil += inputUtil[i];
            if(holderUtil > maxUtil) maxUtil = holderUtil;
        }
        counter++;
    }
    out << maxUtil <<endl;
    in.get();
    }
    return 0;
}

    bool swapper(int array[], int array1[], int size){
		int hold;
		int hold1;
		bool swapped = false;
		for(int i = 0; i < size-1; i++){
			if(array[i] > array[i+1]){
				hold = array[i];
				array[i] = array[i+1];
				array[i+1] = hold;

                hold1 = array1[i];
				array1[i] = array1[i+1];
				array1[i+1] = hold1;
				swapped = true;
			}
		}
		return swapped;
	}

	void sort(int array[], int array1[], int size){
		bool unsorted = true;
		while(unsorted){
			unsorted = swapper(array, array1, size);
		}
	}