Background

Translation source: loj #5457. 「ROI 2012 Day 1」杏干。

Problem Description

In ancient times, the Golden Horde collected gold coins as tribute every year. The famous Crimean Khan Giray decided to play a trick: when paying tribute of $N$ gold coins, he mixed in one lighter counterfeit coin. This was reported to the Golden Horde’s treasurer. To find the counterfeit coin, the treasurer decided to use a magical balance powered by dried apricots.

On each side of the magical balance, a pile of gold coins is placed. The balance can tell whether the two piles have the same weight. If the weights are different, it will indicate which pile is lighter. If the weights are the same, the balance consumes $R$ dried apricots; if the weights are different, it consumes $U$ dried apricots.

As a lover of dried apricots, the treasurer wants to find the counterfeit coin while saving as many dried apricots as possible.

You need to write a program that, given the number of coins $N$ (with exactly one lighter counterfeit coin), computes the minimum number of dried apricots needed to guarantee finding the counterfeit coin.

Input Format

The input file contains only one line with three integers $N, R, U$ $(2 \leq N \leq 1000000, 1 \leq R, U \leq 1000000)$, representing the number of coins, the number of dried apricots consumed when the weights are equal, and the number of dried apricots consumed when the weights are different. The three numbers are separated by spaces.

Output Format

The output file should contain one integer, indicating the minimum number of dried apricots needed to guarantee finding the counterfeit coin.

4 3 1

2

3 3 1

3

15 2 3

8

10 2 1

3

Hint

The detailed additional constraints and scores for each subtask are shown in the table below.

Translated by ChatGPT 5