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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cassert>
using namespace std;

typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define FOR(i, a, b) for (ll i = (a); i < (ll)(b); ++i)
#define FOREQ(i, a, b) for (ll i = (a); i <= (ll)(b); ++i)
#define DEC(i, k) for (ll i = (k); i >= 0; --i)
#define FORIT(i, c) for (__tyoeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define SZ(v) (ll)((v).size())
#define MEMSET(v, h) memset((v), (h), sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())
#define ALL(c) (c).begin(), (c).end()

ll ticket[1000];
ll ticketSum[1000];
ll n, m, a, b, p, q;
ll cnt;

ll calc(ll depth, ll lm) {
  if (depth == cnt || lm <= 0) { return abs(lm); }
  if (ticketSum[depth] < lm) { return abs(lm - ticketSum[depth]); }
  ll ret = m;
  ret = min(ret, calc(depth + 1, lm));
  ret = min(ret, calc(depth + 1, lm - ticket[depth]));
  return ret;
}

int main() {
  cin >> n >> m >> a >> b >> p >> q;
  if (a == 1 && b == 1) {
    ll use = m / (p + q);
    use = min(use, n - 1);
    printf("%lld\n", min(m - use * (p + q), abs(m - (use + 1) * (p + q))));
    return 0;
  }
  cnt = 0;
  {
    ll left = p;
    ll right = q;
    REP(i, n) {
      if (left + right > 2 * m) { break; }
      ticket[cnt++] = left + right;
      ll pleft = left;
      ll pright = right;
      left *= a;
      right *= b;
      if (left / a != pleft || right / b != pright) { break; }
    }
  }
  reverse(ticket, ticket + cnt);
  MEMSET(ticketSum, 0);
  for (ll i = cnt; i > 0; i--) {
    ticketSum[i - 1] = ticket[i - 1] + ticketSum[i];
  }
  ll ans = calc(0, m);
  printf("%lld\n", ans);
}