Optimal Hierarchical Decision Making

The Society for Saving the World has called its \(N\) members to an emergency congress in order to agree on a plan for saving the world. In each meeting, the participants follow this process:

1. Each participant presents his/her proposal which takes \(P\) minutes.
2. After all presentations, they vote for the best proposal, which takes \(V\) minutes.

If a meeting is held with all \(n\) participants together (with \(n>1\)), then the total time of that meeting is \(n \times P + V\) minutes. Note that a subgroup of a single member makes a decision in no time, i.e. \(T(1)=0\), because there is no need to present one’s own proposal.

To minimize the overall decision time, the participants can split themselves into groups, decide internally, and then have the representatives meet. If a meeting is split into \(k\) groups with sizes \(n_1, n_2, \dots, n_k\) (each \(n_i \ge 1\) and \(\sum_{i=1}^{k} n_i = N\)), then:

• Each group meets in parallel to decide on its best proposal. The time required for a group of size \(m\) is \(T(m)\) (with \(T(1)=0\)).
• Afterwards, the \(k\) representatives meet. In that meeting the time is \(k \times P + V\) minutes.

Thus, if we split \(N\) participants into \(k\) groups optimally (i.e. the groups are balanced so that the worst-case subgroup has \(\lceil N/k \rceil\) members), the time required is:

[ T(N) = \min\Bigl{ N \times P + V, ; \min_{2 \le k \le N}\Bigl[ T(\lceil N/k \rceil) + (k \times P + V) \Bigr] \Bigr}. ]

Your task is to compute the minimal time needed for \(N\) participants to reach a decision, given the presentation time \(P\) and voting time \(V\), assuming they organize their meetings optimally.

inputFormat

The input consists of a single line containing three integers \(N\), \(P\), and \(V\) separated by spaces:

• \(N\): the number of participants.
• \(P\): the time (in minutes) spent for each proposal presentation.
• \(V\): the time (in minutes) spent for voting.

Note: For a subgroup of size 1, the decision time is 0.

outputFormat

Output a single integer, the minimal number of minutes needed for the \(N\) participants to reach a decision.

sample

1 1 1

0