import java.util.Scanner;

public class B_1106 {
    static int[] price;
    static int[] person;
    static int goal, N;
    static int[] dp;

    public static int sol(int n){
        if(n <= 0) return 0;
        if(dp[n] != Integer.MAX_VALUE) return dp[n];
        for(int i=1; i<=N; i++){
            dp[n] = Math.min(dp[n], price[i]+sol(n-person[i]));
        }
        return dp[n];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        goal = sc.nextInt();
        N = sc.nextInt();
        price = new int[N+1];
        person = new int[N+1];
        dp = new int[goal+1];
        for(int i=1; i<=N; i++){
            price[i] = sc.nextInt();
            person[i] = sc.nextInt();
        }
        for(int i=0; i<=goal; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        System.out.println(sol(goal));
    }
}