#include <cstdio>

int D[1001][5001];
int e[1001], c[1001];

inline int min( int a, int b ) {
    if( a == -1 )
        return b;
    if( b == -1 )
        return a;
    return a < b ? a : b;
}

inline int V( int a ) {
    if( a == -1 )
        return 0;
    return a;
}

int main () {

    FILE *f, *g;
    f = fopen( "energii.in", "r" );
    g = fopen( "energii.out", "w" );

    int G, w;

    fscanf( f, "%d%d", &G, &w );

    for( int i = 1 ; i <= w ; ++i )
        fscanf( f, "%d%d", &e[i], &c[i] );

    for( int j = 1 ; j <= w ; ++j )
        D[1][j] = e[1] >= j ? c[1] : -1;

    for( int i = 2 ; i <= G ; ++i ) {
        for( int j = 1 ; j <= w ; ++j ) {
            if( j < e[i] )
                D[i][j] = min( D[i-1][j], c[i] );
            else
                D[i][j] = min( D[i-1][j], V(D[i-1][j - e[i]]) + c[i] >= j ? V(D[i-1][j - e[i]]) + c[i] : -1 );
        }
    }

    fprintf( g, "%d\n", D[G][w] );

    fclose( f );
    fclose( g );

    return 0;
}