//BISMILLAHIR RAHMANIR RAHIM
#include <bits/stdc++.h>
#define mem(a, b) (memset(a, b, sizeof(a)))
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define INF 100000000
#define MOD 1000000007
#define MAX 100005
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
typedef vector<ii> vii;
typedef priority_queue<int,vector<int>,greater<int> > PQ;

int Set(int mask, int pos){return mask = mask | (1<<pos);}
bool check(int mask, int pos){return (bool)(mask & (1<<pos));}

int dp[10005][1005];
int a[1005], b[1005], h;
int n;

int solve(int amnt, int pos)
{
    if(pos >= n && amnt < h)
        return INF;
    if(amnt >= h)
        return 0;
    if(dp[amnt][pos] != -1)
        return dp[amnt][pos];

    int ret = INF;
    ret = min(ret, b[pos] + solve(amnt + a[pos], pos));
    ret = min(ret, solve(amnt, pos + 1));
    ret = min(ret, b[pos] + solve(amnt + a[pos], pos + 1));

    return dp[amnt][pos] = ret;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>h>>n;

    for(int i = 0; i < n; i++){
        cin>>a[i]>>b[i];
    }

    memset(dp, -1, sizeof(dp));
    int res = solve(0, 0);

    cout<<res<<endl;

    return 0;
}

/*


M

Basic_Heap_PQ_API_Practice

Please read the Main.cpp file for question.

You have to implement functional heap & sorting APIs.

 

[The description of each function is as follows (based on C / C ++)]

 

//Any init needed to initialize heap, called at the start of each TC

void Heap_init();

 

//Insert  new key k

void Heap_insert (int k);

 

//remove minimum element from minheap, if empty, return -1

int Heap_deleteMin();

 

//Check if the heap is empty

bool Heap_isEmpty();

//Decrease value of key at index "idx" to new_val. If index "idx" is out of range from heap bounds, do nothing. Index "idx" starts from 1.

void Heap_decreasekey (int key, int new_val);

 

//Returns the current size of heap

int Heap_size();

//Get the sorted content in increasing order for the elements currently contained in heap in "arr", memory of arr is sufficient

void Get_Sorted_Heap_Content(int * arr);

 

Input Output format is explained below

 

Input Format

The first line contains number of queries Q.

This is followed by Q lines with each query.

Constraints

1 <= Q <= 10^7

0 <= key <= 10^8

Output

As per the main implementation

 

Sample Input

7

5

0 4

0 9

1

2 1 5

1

4

0 4

0 9

2 1 3

4

4

0 9

0 4

2 1 3

4

4

0 9

0 4

2 1 3

3

5

0 9

1

0 4

2 1 3

3

5

0 9

1

0 4

2 0 3

4

5

0 9

0 4

2 2 3

4

3

 

Sample Output

4

5

3 9 

3 9 

2

9

1

9

4 

3 4 

2

 

[How to write Code]

1.       There are 2 files Main code and User code

-      Main part: This code can not be modified.

-      User Code section: This is the code that you should write. When submitting it, the code should not include library functions as well as standard input / output functions (they are done in Main.cpp).

2.       Precautions for programming in Local PC

-      Copy and use the code in the Main section.

-      To use sample_input.txt, you need to uncomment the code in the main section (commented out) that converts the standard input into a file.

-      When you write the code of the User Code and submit it to the server, you should delete all standard input / output functions as well as library functions for debugging.

3.       We do not specify all of the constraints in the problem, so we need to analyze the given code (Main Code).

 

[Notes for this question]

1.       The candidate must implement all the extern APIs mentioned before in the User Code section:

a.       void Heap_init();

b.      void Heap_insert (int k)

c.       int Heap_deleteMin()

d.      bool Heap_isEmpty()

e.      void Heap_decreasekey (int key, int new_val)

f.        int Heap_size()

g.       void Get_Sorted_Heap_Content(int *arr)

 

2.       At the time of submission, delete header files and standard input / output functions such as printf and cout (which were used for debugging) , and submit them .

3.       It is possible to add global variables in the User Code part and functions created by the candidate.

4.       The Main part can not be modified and is used as it is for actual scoring.

5.       The semantics of the function must be determined by analysing the main part directly.

 
Sample Input :  sample_input.txt sample_input pop-up 
Try Count 0
Total Count 50
More View  


Submission Time

Solution

Result





Language C(gcc-4.8.2)  C++(gcc-4.8.2)  JAVA(java-1.8.0_192)  Python(PyPy-7.0)   Initialize the source code 
Main 



























54
        return;



55
    }



56
​



57
    for (int i = 0; i < cnt; i++)



58
        printf("%d ", arr[i]);



59
    printf("\n");



60
}



61
static void init()



62
{



63
    for (int i = 0; i < MAX_COUNT; i++)



64
        arr[i] = 0;



65
​



66
    Heap_init();



67
}



68
​



69
int main()



70
{



71
    setbuf(stdout, NULL);



72
    //freopen("sample_input.txt", "r", stdin);



73
    //freopen("output1.txt","w",stdout);



74
    int T, N, cmd;



75
    scanf("%d", &T);



76
​



77
    for (int tc = 1; tc <= T; tc++)



78
    {



79
        scanf("%d", &N);



80
        init();



81
​



82
        for (int i = 0; i < N; i++)



83
        {



84
            int idx;



85
            scanf("%d", &cmd);



86
​



87
            switch(cmd)



88
            {



89
            case 0:



90
                scanf("%d", &idx);



91
                Heap_insert (idx);



92
                break;



93
            case 1:



94
                print_and_extract_heap();



95
                break;



96
            case 2:



97
                int newval;



98
                scanf("%d %d ", &idx, &newval);



99
                Heap_decreasekey(idx, newval);



100
                break;



101
            case 3:



102
                print_sizeof_heap();



103
                break;



104
            case 4:



105
                Get_Sorted_Heap_Content(arr);



106
                print_sorted_arr(arr);



107
                break;



108
            }



109
        }



110
    }



111
}




User code(user.cpp) 














































1
​



2
void Heap_init()



3
{



4
}



5
​



6
void Heap_insert (int k)



7
{



8
}



9
​



10
int Heap_deleteMin()



11
{



12
    return 0;



13
}



14
​



15
bool Heap_isEmpty()



16
{



17
    return false;



18
}



19
​



20
void Heap_decreasekey (int key, int new_val)



21
{



22
}



23
​



24
int Heap_size()



25
{



26
    return 0;



27
}



28
​



29
void Get_Sorted_Heap_Content(int *arr)



30
{



31
​



32
}

*/

Measured memory_bytes: 40192