디버깅

디버거는 이번 문제에 도움이 되지 않는다. 디버그 빌드와 릴리스 빌드에서 코드가 다르게 동작하는 경로는 여러 가지이고, 그런 일이 벌어지면 더 원시적인 방법으로 돌아가야 한다.

그래서 릴리스 빌드를 죽이는 코드 한 줄을 찾는 일은 이제 나와 printf의 몫이다. 다행인 점이 하나 있다. printf를 넣어도 버그는 그대로이고, 프로그램은 여전히 원래와 같은 줄에서 죽는다. 실행 시간도 눈에 띄게 달라지지 않는다. 그래서 모든 줄 앞에 printf를 하나씩 넣고, 죽을 때까지 실행한 다음, 마지막으로 출력된 줄을 확인하는 단순한 방법도 통한다.

하지만 printf를 하나 넣는 데도 시간이 걸리고 프로그램의 줄 수는 아주 많을 수 있다. 그래서 printf를 코드 한가운데에 하나만 넣고 실행해서, 추가한 줄보다 앞에서 죽는지 확인한 뒤 앞쪽 절반이나 뒤쪽 절반에서 탐색을 이어가는 편이 나을 수도 있다.

그런데 프로그램을 한 번 실행하는 데도 시간이 오래 걸리므로, 가장 빠른 전략은 보통 두 방법의 중간 어딘가에 있다. 죽는 줄이 어디에 있든 상관없이, 최적 전략으로 그 줄을 찾는 데 걸리는 최악의 시간을 구하는 프로그램을 작성하시오.

정확한 규칙은 다음과 같다. 프로그램은 $n$줄이고 그중 정확히 한 줄에서 죽는다. 한 번 실행하기 전에 printf 문을 원하는 만큼 넣을 수 있고, 하나를 넣는 데 $p$의 시간이 든다. 앞선 단계에서 넣은 printf는 그대로 남아 있다. 한 번 실행하는 데 $r$의 시간이 들고, 실행하면 죽기 직전에 마지막으로 출력된 printf가 무엇인지 알 수 있다. 죽는 줄의 후보가 하나만 남으면 탐색이 끝난다.

첫째 줄에 정수 세 개가 주어진다.

• $n$ ($1 \le n \le 10^6$): 코드의 줄 수
• $r$ ($1 \le r \le 10^9$): 프로그램을 컴파일하고 죽을 때까지 실행하는 데 걸리는 시간
• $p$ ($1 \le p \le 10^9$): printf 한 줄을 넣는 데 걸리는 시간

프로그램은 이미 한 번 실행해 봤으므로 어딘가에서 죽는다는 사실은 알고 있다.

최적 전략으로 죽는 줄을 찾는 데 걸리는 최악의 시간을 정수 하나로 출력한다.