UVa 1648

#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int BSlo(int n, int u, int d){
    int lo = 0, hi = n, mid, ans;

    while(lo <= hi){
        mid = (lo + hi)/2;
        int floor = (u * mid) - (d * (n-mid));
        if(floor > 0){
            ans = floor;
            hi = mid -1;
        }
        else{
            lo = mid + 1;
        }
    }
    return ans;
}

int main(){
    #ifdef ERFANUL007
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n, m;
    while(cin >> n >> m){
        int ans = INT_MAX;

        while(m--){
            int u, d;
            cin >> u >> d;
            ans = min(ans, BSlo(n, u, d));
        }
        cout << ans << '\n';
    }

    #ifdef ERFANUL007
        fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    #endif

    return 0;
}