Rex and Energy

Problem Statement

Rex and Energy Rex is given four integers n , k , A and B . Initially he holds a value x = n , and he wants to reduce it to 1 by repeatedly performing either of the following two operations: Subtract 1 from x. This operation costs A units of energy and may be performed whenever x > 1 . Divide x by k. This operation may be performed only when x is divisible by k , and it costs B units of energy. Rex may perform these operations any number of times, in any order, until x becomes 1 . Determine the minimum total energy required to reduce x to 1 . Input Format The first line contains an integer n . The second line contains an integer k . The third line contains an integer A . The fourth line contains an integer B . Output Format Print a single 64-bit integer — the minimum total energy required to reduce x to 1 . Constraints 1 <= n <= 2 * 10^9 1 <= k <= 2 * 10^9 1 <= A <= 2 * 10^9 1 <= B <= 2 * 10^9 The answer never exceeds (n - 1) * A <= 4 * 10^18 , so it alway