easy math problem

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

对于一个数n,有以下两种操作:

一是减一,需要花费 a 。

但是如果 n 能被 k 整除,还可以花费 b 让 n 除以 k。

请问将这个数变为1最少要多少花费?

Input

第一行一个整数n(n<=1e5)

第二行三个正整数分别为a, b, k ( 0 < a , b , k <= n ,n*a<1e9 ).

Output

输出一个整数代表最小花费。

Sample Input

10
1 2 2

Sample Output

6

Hint

Source

行走的二叉树