#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use proconio::*;
use std::collections::VecDeque;
use std::io::stdin;
use std::str::FromStr;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let hp = sc.next_usize();
    let n = sc.next_usize();
    let mut damage = Vec::with_capacity(n);
    let mut magic = Vec::with_capacity(n);

    for _i in 0..n {
        let a = sc.next_usize();
        let b = sc.next_usize();
        damage.push(a);
        magic.push(b);
    }

    let damage = damage;
    let magic = magic;

    let mut dp = vec![vec![U_INF; hp + 10]; n + 10];

    dp[1][0] = 0;

    for i in 1..=n {
        for j in 0..=hp {
            if j + damage[i - 1] >= hp {
                dp[i][hp] = dp[i][hp].min(dp[i][j] + magic[i - 1]);
            } else {
                dp[i][j + damage[i - 1]] = (dp[i][j + damage[i - 1]]).min(dp[i][j] + magic[i - 1]);
            }
            dp[i + 1][j] = (dp[i + 1][j]).min(dp[i][j]);
        }
    }

    let mut min = U_INF;
    for i in 0..=n {
        min = (min).min(dp[i][hp]);
    }

    println!("{}", min);
}

pub struct Scanner {
    buf: VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect_vec()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn fill_vec_line<T: FromStr>(&mut self, v: &mut Vec<T>) {
        for vi in v {
            *vi = self.next();
        }
    }

    pub fn fill_vec<T: FromStr>(&mut self, v: &mut Vec<Vec<T>>) {
        for vi in v {
            for vii in vi {
                *vii = self.next();
            }
        }
    }

    pub fn make_vec_line<T: FromStr + Default + Clone>(&mut self, i: usize) -> Vec<T> {
        let mut v = vec![Default::default(); i];
        self.fill_vec_line(&mut v);
        v
    }

    pub fn make_vec<T: FromStr + Default + Clone>(&mut self, i: usize, j: usize) -> Vec<Vec<T>> {
        let mut v = vec![vec![Default::default(); j]; i];
        self.fill_vec(&mut v);
        v
    }
}


Measured memory_bytes: 81136