22565번 - Nearest Station 다국어

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

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

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

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