Our Tanya은 Crying Out Loud이다

지금 당장은 실제로 그렇지 않다. 하지만 당신이 이 문제를 풀지 않으면 그렇게 될 것이다.

정수 n, k, A and B가 주어진다. 수 x가 있으며, 처음에는 n과 같다. 다음 두 가지 연산을 수행할 수 있다.

1. x에서 1을 뺀다. 이 연산에는 A개의 동전이 든다.
2. x를 k로 나눈다. x가 k로 나누어떨어질 때만 수행할 수 있다. 이 연산에는 B개의 동전이 든다.

x를 1로 만들기 위해 지불해야 하는 동전의 최소 개수는 얼마인가?

첫 번째 줄에 하나의 정수 n가 주어진다. (1 ≤ n ≤ 2·109)

두 번째 줄에 하나의 정수 k가 주어진다. (1 ≤ k ≤ 2·109)

세 번째 줄에 하나의 정수 A가 주어진다. (1 ≤ A ≤ 2·109)

네 번째 줄에 하나의 정수 B가 주어진다. (1 ≤ B ≤ 2·109)

x를 1로 만들기 위해 지불해야 하는 동전의 최소 개수를 나타내는 하나의 정수를 출력한다.

첫 번째 테스트 케이스에서 최적의 전략은 다음과 같다.

• 동전 3개를 지불하고 x에서 1을 뺀다(9 → 8).
• 동전 1개를 지불하고 x를 2로 나눈다(8 → 4).
• 동전 1개를 지불하고 x를 2로 나눈다(4 → 2).
• 동전 1개를 지불하고 x를 2로 나눈다(2 → 1).

총비용은 동전 6개이다.

두 번째 테스트 케이스에서 최적의 전략은 x에서 1을 4번 빼고 총 동전 8개를 지불하는 것이다.