/* paiza POH! vol.3
 * result:
 * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/3e55de48187072f33d6db840d5addb86
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>
int main(void){
    int m, n;
    int q[50] = {0};
    int r[50] = {0};
    int i;
    
    int a0, a1, b0, b1, c0;
    int sum_q, sum_r, min;
    
    scanf("%d", &m);
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%d %d", &q[i], &r[i]);
    }
    
    if (n > 25) {
        b0 = 0;
        b1 = 1 << (n - 25);
    } else {
        b0 = 1 << n;
        b1 = 0;
    }
    
    a0 = 1;
    a1 = 0;
    c0 = 1 << 25;
    min = 250000000;
    for (;;) {
        if (a1 > b1) {
            break;
        } else if (a1 == b1 && a0 > b0) {
            break;
        }
        if (a0 == c0) {
            a0 = 0;
            a1++;
        }
        sum_q = sum_r = 0;
        for (i = 0; i < 25; i++) {
            if ((a0 >> i) & 1) {
                sum_q += q[i];
                sum_r += r[i];
            }
            if ((a1 >> i) & 1) {
                sum_q += q[i + 25];
                sum_r += r[i + 25];
            }
        }
        if (sum_q >= m && sum_r < min) {
            min = sum_r;
        }
        a0++;
    }
    printf("%d\n", min);
    return 0;
}