No.555 世界史のレポート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 125
作問者 : addeight2addeight2 / テスター : butsurizukibutsurizuki
4 ProblemId : 1305 / 出題時の順位表
問題文最終更新日: 2017-08-12 01:52:37

問題文

addeight君は高校生です。
彼は今、世界史のレポートをパソコンで書いています。
しかし、彼は世界史が苦手で、レポートにはまだアルファベットのAしか書かれていません。
レポートには\(N\)文字以上書かれてないと、世界史の怖い先生に怒られてしまいます。
そこで、addeight君はコピーとペーストだけで\(N\)文字以上の文字列を作ることにしました。
コピーをするとレポートのすべての文字列がクリップボードにコピーされ、ペーストをするとレポートの文字列の後ろにクリップボードの文字列が追加されます。
コピー、ペーストにはそれぞれ\(C\),\(V\)だけコストがかかります。\(N\)文字以上作る最小のコストを求めてください。

クリップボードの初期状態は、空文字列です。

入力

N
C V

\(2 \leq N \leq 50000\)
\(1 \leq C , V \leq 1000\)

出力

\(N\)文字以上作るのにかかる最小のコストを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
6
3 2
出力
12

操作レポートの文字列クリップボードの文字列
始めの状態A
コピーAA
ペーストAAA
コピーAAAA
ペーストAAAAAA
ペーストAAAAAAAA
コピーを2回、ペーストを3回行ったので合計のコストは12です。 また、コピー、ペースト、ペースト、コピー、ペーストでも12のコストで6文字作ることができます。

サンプル2
入力
10
1 3
出力
15

コピー、ペースト、コピー、ペースト、コピー、ペースト、ペーストで12文字をコスト15で作れます。他にもコスト15で10文字以上作る方法があります。

サンプル3
入力
100
1000 1
出力
1099

コピーの後ペーストを99回行います。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。