bool test(ll a, ll b) {
    // return true if (true value) >= a/b
    ll n = 0, m = 1;

    rep(i, N) {
        if (n < m*A[i].fi) n = A[i].fi, m = 1;

        ll c = b*n+m*a, d = m*b;
        ll g = gcd(c, d);
        n = c/g;
        m = d/g;

        if (n > m*A[i].se) return false;
    }
    return true;
}

pair<ll, ll> stern_brocot(ll M, ll N) {
    // M : max value
    // N : max divisor
    // if result is a/b, return as {a, b}
    ll a = 0, b = 1; // l
    ll c = 1, d = 0; // r
    int l, r;
    bool chg = true;

    while(chg) {
        chg = false;

        // to left
        l = 0, r = (N-d-1)/b+1;
        while(l < r) {
            int mid = (l+r+1)/2;
            if (test(a*mid+c, b*mid+d)) {
                r = mid-1;
            } else {
                l = mid;
            }
        }

        c += a*l;
        d += b*l;
        chg |= (l > 0);

        // to right
        l = 0, r = (d?(N-b-1)/d+1:M);
        while(l < r) {
            int mid = (l+r+1)/2;
            if (test(a+mid*c, b+mid*d)) {
                l = mid;
            } else {
                r = mid-1;
            }
        }

        a += c*l;
        b += d*l;
        chg |= (l > 0);
    }

    return {a, b};
}