Problem Statement

Minimum Cost to Reduce N to 1 You are given an integer N and the costs of three operations: Subtract 1 from the current value, costing X . Divide the current value by 2 when it is divisible by 2 , costing Y . Divide the current value by 3 when it is divisible by 3 , costing Z . Two division operations may not be consecutive. After dividing by 2 or 3 , the next operation must be a subtraction. Find the minimum total cost to reduce N to 1 . Input Format The first line contains N . The second line contains X , the subtraction cost. The third line contains Y , the divide-by-2 cost. The fourth line contains Z , the divide-by-3 cost. Output Format Print the minimum total cost. Constraints 1 ≤ N ≤ 100,000 1 ≤ X, Y, Z ≤ 1,000 32-bit signed arithmetic suffices for the answer under these bounds. Examples Example 1 Input: 10 1 2 3 Output: 6 Explanation: One optimal sequence is 10 -> 5 -> 4 -> 2 -> 1 , with operation costs 2 + 1 + 2 + 1 . Example 2 Input: 18 2 1 1 Output: 7 Explanation