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 <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll labs(ll x){
	if(x<0LL)return -x;
	return x;
}

int zcnt(ll x){
	int cnt=0;
	while(x>0){
		x/=10LL;
		cnt++;
	}
	return cnt;
}

ll n,m,a,b,p,q;
ll num[51];
vector<ll> vec;

int main(void){
	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&p,&q);
	if(a==1LL && b==1LL){
		ll dist=p+q;
		ll cnt=m/dist;
		printf("%lld\n",min(labs(m-min(cnt,n)*dist),labs(m-(min(cnt+1LL,n))*dist)));
	}else{
		ll v=0;
		ll np=p,nq=q;
		while(np+nq<=m){
			num[v]=np+nq;
			if(zcnt(np)+zcnt(a)>=zcnt(m)+4 || zcnt(nq)+zcnt(b)>=zcnt(m)+4)break;
			np*=a;
			nq*=b;
			v++;
		}
		num[v]=np+nq;
		v++;
		ll res=m;
		v=min(v,n);
		if(v==0){
			res=min(res,labs(m-p-q));
			printf("%lld\n",res);
			return 0;
		}
		int v2=(int)v/2;
		for(int bit=0;bit<(1<<v2);bit++){
			ll now=0;
			for(int i=0;i<v2;i++){
				if((bit>>i) & 1){
					now+=num[i];
				}
			}
			vec.push_back(now);
		}
		sort(vec.begin(),vec.end());
		vec.erase(unique(vec.begin(),vec.end()),vec.end());
		int v3=v-v2;
		for(int bit=0;bit<(1<<v3);bit++){
			ll now=0;
			for(int i=0;i<v3;i++){
				if((bit>>i) & 1){
					now+=num[i+v2];
				}
			}
			int l=lower_bound(vec.begin(),vec.end(),m-now)-vec.begin();
			if(l<vec.size())res=min(res,labs(m-now-vec[l]));
			if(l>0 || l==vec.size()){
				res=min(res,labs(m-now-vec[l-1]));
			}
		}
		printf("%lld\n",res);
	}
	return 0;
}