Minimum Coins to Reach a Multiple

You are given positive integers n, k, a, b and m. You can perform the following two types of operations any number of times (possibly zero):

• Operation 1: Choose an integer \( x \) satisfying \(0 \le x < k\) and change \( n \) to \( k \cdot n + x \). This operation costs \( a \) coins.
• Operation 2: Change \( n \) to \( \lfloor \frac{n}{k} \rfloor \). This operation costs \( b \) coins. (Here, \( \lfloor \cdot \rfloor \) denotes the floor function.)

Your task is to compute the minimum number of coins required to change n into a multiple of m (note that 0 is considered a multiple of any positive integer).

All formulas are given in LaTeX format. For example, the first operation is described by the formula: $$n \to k\cdot n+x, \quad 0 \le x < k.$$

inputFormat

The input consists of a single line with five space-separated positive integers:

n k a b m

It is guaranteed that k ≥ 2 and all numbers are positive.

outputFormat

Output a single integer representing the minimum number of coins needed to change n into a multiple of m.

sample

1 10 5 2 2

2