うさぎがある電車のチケットをn 枚持っている. チケットにはそれぞれ0 からn − 1 までの番号がついていて, k 番のチケットを使うと, p⋅ak + q⋅bk 駅進むことができる.
うさぎは今いる駅からm 駅進んだ駅にあるニンジン食べ放題の店に行きたいが, なるべく歩く距離を短くしたい. 駅は等間隔に並んでいる. チケットを電車の上り線で進むことのみに用いるとき, うさぎは最小何駅分の徒歩で店に着けるか.
1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (整数)
うさぎは最小何駅分の徒歩で店に着けるか, その数を一行に出力せよ.
cho.sh