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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int main(){

	int POW[22];
	for(int i = 0; i < 22; i++)POW[i] = pow(2,i);

	ll N,M,A,B,P,Q;

	scanf("%lld %lld %lld %lld %lld %lld",&N,&M,&A,&B,&P,&Q);

	if(A == 1 && B == 1){

		ll num = M/(P+Q);

		if(num >= N){
			printf("%lld\n",M-N*(P+Q));
		}else{
			printf("%lld\n",min(M%(P+Q),(num+1)*(P+Q)-M)); //少し足りないと、少し多いの、差が小さい方
		}

		return 0;
	}

	vector<ll> FIRST;

	ll tmp = P+Q;
	ll a = 1, b = 1;
	ll count = 0,over_count = 0;

	double check;

	while(true){

		if(tmp > M)over_count++; //超過は1回だけ許す

		FIRST.push_back(tmp);
		count++;
		if(count == N || over_count == 1)break;

		check = P*a*A+Q*b*B;
		if(check > (double)M)break;

		a *= A;
		b *= B;

		tmp = P*a+Q*b;
	}

	//数字を2つのグループに振り分ける
	vector<ll> G[2];
	for(ll i = 0; i < FIRST.size(); i++){
		if(i <= (FIRST.size())/2){
			G[0].push_back(FIRST[i]);
		}else{
			G[1].push_back(FIRST[i]);
		}
	}

	int num[2];
	num[0] = (int)G[0].size();
	num[1] = (int)G[1].size();

	//各グループで数字を作る
	vector<ll> V[2];
	V[1].push_back(0);
	for(int group = 0; group < 2; group++){
		for(int state = 0; state < POW[num[group]]; state++){
			tmp = 0;
			for(int loop = 0; loop < num[group]; loop++){
				if(state & (1 << loop)){
					tmp += G[group][loop];
				}
			}
			V[group].push_back(tmp);
		}
		sort(V[group].begin(),V[group].end());
		V[group].erase(unique(V[group].begin(),V[group].end()),V[group].end());
	}

	ll ans = M,tmp_ans;

	int left,right,m,loc;

	for(int i = 0; i < V[0].size(); i++){

		if(V[0][i] >= M){
			ans = min(ans,V[0][i]-M);
			break;
		}

		//2分探索で、和がMを超えない、最大のindexを求める
		left = 0,right = (int)V[1].size()-1,m = (left+right);
		loc = 0;

		while(left <= right){
			if(V[0][i]+V[1][m] <= M){
				loc = m;
				left = m+1;
			}else{
				right = m-1;
			}
			m = (left+right)/2;
		}

		tmp_ans = (M-(V[0][i]+V[1][loc]));
		if(loc < (int)V[1].size()-1){
			tmp_ans = min(tmp_ans,V[0][i]+V[1][loc+1]-M);
		}

		ans = min(ans,tmp_ans);
	}

	printf("%lld\n",ans);

	return 0;
}

