Debugging

Your debugger is no help here. Code can behave differently between a debug build and a release build in many ways, and when that happens you fall back to more primitive methods.

So it is you and printf against a release build that crashes, and you have to find the line of code that causes it. One thing works in your favour. Adding printf statements does not change the bug, and the program still crashes on the same original line. It does not change the running time in any noticeable way either. So even the naive plan works: put a printf before every line, run the program until it crashes, and read the last line it printed.

Adding each printf takes time, though, and the program may have a great many lines. A better plan might put a single printf in the middle of the code, run the program, check whether the crash happens before the added line, and then continue the search in either the first or the second half.

But running the program also takes a long time, so the fastest strategy is usually somewhere in between. Compute the minimum worst-case time to find the crashing line under an optimal strategy, no matter where that line is.

The exact rules are as follows. The program has $n$ lines and exactly one of them crashes. Before each run you may add as many printf statements as you want, and adding one costs $p$ time. Every printf added in an earlier step stays in place. A run costs $r$ time and tells you which printf was the last one printed before the crash. The search ends once a single candidate line remains.

The first line contains three integers.

• $n$ ($1 \le n \le 10^6$): the number of code lines
• $r$ ($1 \le r \le 10^9$): the time it takes to compile and run the program until it crashes
• $p$ ($1 \le p \le 10^9$): the time it takes to add a single printf line

You have already run the program once, so you know that it does crash somewhere.

Print one integer, the worst-case time to find the crashing line under an optimal strategy.