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 <iostream>
#include <cmath>
using namespace std;

int main(){
  long long int n, m, a, b, p, q, ans;
  cin >> n >> m >> a >> b >> p >> q;
  if(a < b){
    swap(a, b);
    swap(p, q);
  }
  if(a == 1LL){
    if(m/(p + q) >= n) cout << m - n*(p + q) << endl;
    else{
      long long int t = m - m/(p + q)*(p + q);
      cout << min(t, p + q - t) << endl;
    }
    return 0;
  }
  ans = m;
  long long int x = 1LL, y = 1LL;
  for(int i = 1; i < n; ++i){
    if(m <= p*x + q*y) break;
    if(x > (1LL<<40)/a || y > (1LL<<40)/b) break;
    x *= a;
    y *= b;
  }

  while(x > 0){
    ans = min(ans, abs(m - (p*x + q*y)));
    if(m >= p*x + q*y) m -= p*x + q*y;
    x /= a;
    y /= b;
  }
  cout << ans << endl;
  return 0;
}

