题目描述

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

小智的宠物名字叫皮卡丘。初始，皮卡丘的 STR 值为 $X$，EXP 值为 $0$。小智可以带宠物到以下任意一个训练馆进行训练：

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

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

4 20 2 10

输出 #1

2

输入输出样例 #2

输入 #2

1 1000000000000000000 10 1000000000

输出 #2

1000000007

数据范围

对于 $100\%$ 的数据， $1 \le x \lt y \le 10^{18} , 2 \le A \le 10^9 , 1 \le B \le 10^9$ 。