题目描述

いろはちゃんはペットを育てるゲームにはまっています。

いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の 強さ は $X$ 、経験値 は $0$ です。 これらの値は次の $2$ 種類の特訓によって増加します。

• カコモンジムに通う：強さが $A$ 倍になり、経験値は $1$ 増える。
• AtCoderジムに通う：強さが $B$ 増え、経験値は $1$ 増える。

高橋君は強さが $Y$ 以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。

そこで、強さが $Y$ 以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$X$ $Y$ $A$ $B$

输出格式

与えられた条件の下での経験値の最大値を出力せよ。

题目大意

题目描述

Iroha 正在玩一个宠物养成的游戏。

Iroha 的宠物名字叫 Takahashi。初始，Takahashi 的 STR 值为 $X$，EXP 值为 $0$。Iroha 可以带宠物到以下任意一个 Gym 进行训练：

• Kakomon Gym：STR 值将会变为原来的 $A$ 倍，EXP 值将会加上 $1$。
• AtCoder Gym：STR 值将会加上 $B$，EXP 值将会加上 $1$。

当 Takahashi 的 STR 值大于等于 $Y$，Takahashi 会进化形态。

但是 Iroha 认为进化的 Takahashi 没那么可爱，于是 Iroha 想求出在保证 Takahashi 不进化的情况下，能达到的最大 EXP 值是多少。

输入格式

一行四个整数，$X\ Y\ A\ B$。

输出格式

一行一个表示最大 EXP 值的整数。

4 20 2 10

2

1 1000000000000000000 10 1000000000

1000000007

提示

制約

• $1\ \leq\ X\ <\ Y\ \leq\ 10^{18}$
• $2\ \leq\ A\ \leq\ 10^9$
• $1\ \leq\ B\ \leq\ 10^9$
• 入力は全て整数

Sample Explanation 1

最初、高橋君の強さは $4$ です。次のような特訓方法によって、経験値を $2$ にすることができます。 - まず カコモンジムに通うことで、高橋君の強さは $8$、経験値は $1$ になります。 - 次に、AtCoderジムに通うことで、高橋君の強さは $18$、経験値は $2$ になります。 どのような特訓方法によっても、経験値を $2$ より大きくすることはできません。

Sample Explanation 2

オーバーフローに注意してください。