I have n tickets for a train with a rabbit. Each ticket is numbered from 0 to n − 1, and you can use the k ticket to go to p⋅ak + q⋅bk station.

Rabbit wants to go to the all-you-can-eat carrot shop at the station m station ahead of the current station, but wants to walk as short as possible. The stations are lined up at regular intervals. When using, how many stations can a rabbit walk to reach the store?



Input

1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (integer)

Output

Output the number of rabbits that can reach the store on foot at the minimum number of stations in one line.

Examples

Input

6 200 2 3 4 5


Output

1


Input

6 1 2 3 4 5


Output

1
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

ll solve(ll n, ll m, ll a, ll b, ll p, ll q) {
    if (a == 1 and b == 1) {
        ll delta = p + q;
        ll result = m;
        setmin(result, abs(m - min(n,  m              / delta) * delta));
        setmin(result, abs(m - min(n, (m + delta - 1) / delta) * delta));
        return result;
    }
    vector<ll> tickets;
    for (ll k = 0; k < n; ++ k) {
        double ticket = p * pow(a, k) + q * pow(b, k);
        if (2 * m + 3 < ticket) break;
        tickets.push_back(ticket);
    }
    if (tickets.empty()) {
        return m;
    } else if (tickets.size() == 1) {
        return min(m, abs(m - tickets[0]));
    }
    auto generate = [&](int l, int r) {
        vector<ll> acc;
        acc.push_back(0);
        repeat_from (k, l, r) {
            ll ticket = tickets[k];
            int prev_size = acc.size();
            repeat (i, prev_size) {
                acc.push_back(acc[i] + ticket);
            }
            whole(sort, acc);
            acc.erase(whole(unique, acc), acc.end());
        }
        return acc;
    };
    vector<ll> lower = generate(0, tickets.size() / 2);
    vector<ll> upper = generate(tickets.size() / 2, tickets.size());
    ll result = m;
    for (ll x : lower) {
        int i = whole(lower_bound, upper, m - x) - upper.begin();
        repeat_from (j, max(0, i - 3), min<int>(upper.size(), i + 3)) {
            ll y = upper[j];
            setmin(result, abs(m - (x + y)));
        }
    }
    return result;
}

int main() {
    ll n, m, a, b, p, q; scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &a, &b, &p, &q);
    ll result = solve(n, m, a, b, p, q);
    printf("%lld\n", result);
    return 0;
}