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
def solve():
    n,m,a,b,p,q = map(int,input().split())
    if a==1 and b==1:
        if (p+q)*n <= m:
            return m - (p+q)*n
        else:
            k = m//(p+q)
            return min(m-k*(p+q),(k+1)*(p+q)-m)
    else:
        ans = m
        for i in range(min(n-1,40),-1,-1):
            f = p*(a**i) + q*(b**i)
            if m < f:
                ans = min(ans, f-m)
            else:
                m -= f
            ans = min(ans,m)
        return ans

def main():
    print(solve())

if __name__ == '__main__':
    main()