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<algorithm>
#include<vector>
using namespace std;

typedef long long ll;

int main(){
	ll n,m,a,b,p,q;
	cin >> n >> m >> a >> b >> p >> q;
	
	if(a == 1 && b == 1){
		ll x = m/(p+q);
		if(x >= n)cout << m-n*(p+q) << endl;
		else cout << min ( m-x*(p+q) , (x+1)*(p+q)-m ) << endl;
	}
	else {
		vector<ll> vec;
		ll s = 1 , t = 1;
		for(int i = 0 ; i < n ; i ++){
			vec.push_back(p*s+q*t);
			if(p*s+q*t > m)break;
			s *= a;
			t *= b;
		}
		int N = vec.size();
		vector<ll> A,B;
		A.push_back(0);
		for(int i = 0 ; i < N/2 ; i ++){
			int x = A.size();
			for(int j = 0 ; j < x ; j ++){
				A.push_back(vec[i]+A[j]);
			}
		}
		B.push_back(0);
		for(int i = N/2 ; i < N ; i ++){
			int x = B.size();
			for(int j = 0 ; j < x ; j ++){
				B.push_back(vec[i]+B[j]);
			}
		}
		sort(B.begin(),B.end());
		B.erase(unique(B.begin(),B.end()),B.end());
		ll ret = m;
		for(int i = 0 ; i < A.size() ; i ++){
			int x = upper_bound(B.begin(),B.end(),m-A[i])-B.begin();
			if(x < B.size())ret = min ( ret , A[i]+B[x]-m );
			x --;
			ret = min ( ret , m-A[i]-B[x] );
		}
		cout << ret << endl;
	}
}