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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<53;
ll Sum[100];
ll n,m,a,b,p,q;


ll calc(ll k){
  ll A = 1,B = 1;
  ll res=p+q;
  while(0<res&&res<=INF&&k--)A*=a,B*=b,res=p*A+q*B;
  if(res<0||res>INF)res=INF;
  return res;
}


ll ans = INF;
set<ll> used[101];
void dfs(ll pos,ll sum){
  ans = min(ans,(ll)abs(m-sum));
  if(m<sum||pos==-1||sum<0LL||sum>INF) return;
  if(Sum[pos]+sum<m){ans=min(ans,m-(Sum[pos]+sum));return;}
  if(used[pos].count(sum)) return ;
  used[pos].insert(sum);
  dfs(pos-1,sum+calc(pos));  
  dfs(pos-1,sum);
}


int main(){
  cin>>n>>m>>a>>b>>p>>q;
  for(int i=0;i<60;i++) Sum[i] = INF;
  Sum[0] = calc(0);
  for(int i=1;i<60;i++)Sum[i]=min(INF,calc(i)+Sum[i-1]);

  if(max(a,b)==1) {
    ll s = abs(m - (m/(p+q))*(p+q));
    ll t = abs(m - (m/(p+q))*(p+q) - (p+q));
    if(m/(p+q)==n) t = INF;
    if(m/(p+q)<=n) cout<<min(s,t)<<endl;
    else cout<< m-(p+q)*n <<endl;
    return 0;
  }
  
  dfs(min(n-1,50LL),0);
  cout<<ans<<endl;
  return 0;
}