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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder("");

        int distance, town;
        st = new StringTokenizer(br.readLine());

        distance = Integer.parseInt(st.nextToken());
        town = Integer.parseInt(st.nextToken());
        int[] dp = new int[distance+1];
        dp[0] = Integer.MAX_VALUE;

        for(int i=0; i<town; i++){
            int length, capacity;

            StringTokenizer pipe = new StringTokenizer(br.readLine());

            length = Integer.parseInt(pipe.nextToken());
            capacity = Integer.parseInt(pipe.nextToken());

            // 해당 pipe 의 길이와 같은동안 까지 반복하는 아이디어가 중요하다.
            for(int y=distance; y>=length; y--){
                // 모든 수도관들을 각각 한번식 넣어본다.
                // 그중 가장 큰 capacity를 채택한다.
                dp[y] = Math.max(dp[y], Math.min(capacity, dp[y-length]));

            }
        }
        System.out.println(dp[distance]);
    }
}