Problem H: Nearest Station

うさぎがある電車のチケットをn 枚持っている. チケットにはそれぞれ0 からn − 1 までの番号がついていて, k 番のチケットを使うと, p⋅a^k + q⋅b^k 駅進むことができる.

うさぎは今いる駅からm 駅進んだ駅にあるニンジン食べ放題の店に行きたいが, なるべく歩く距離を短くしたい. 駅は等間隔に並んでいる. チケットを電車の上り線で進むことのみに用いるとき, うさぎは最小何駅分の徒歩で店に着けるか.

Input

1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (整数)

Output

うさぎは最小何駅分の徒歩で店に着けるか, その数を一行に出力せよ.

Sample Input 1

6 200 2 3 4 5

Sample Output 1

1

Sample Input 2

6 1 2 3 4 5

Sample Output 2

1

---