No.915 Plus Or Multiple Operation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 120
作問者 : ningenMeningenMe / テスター : tpynerivertpyneriver
8 ProblemId : 3389 / 出題時の順位表

問題文

くる君は最初$0$枚のクッキーを持っています。くる君はクッキーを$A$枚ちょうどにしたいです。
クッキーを増やすには次の$2$種類の操作があります。

 ・$B$円を支払う。$1$以上$C$未満の数字$i$を一つ選び、クッキーを購入する。クッキーの枚数が$i$増える。
 ・$B$円を支払う。クッキーを叩き割る許可を得ることができ、クッキーの枚数が$C$倍になる。

上記の操作は好きな順番で好きな回数行うことができます。
くる君は出来るだけ少ないお金でクッキーを$A$枚ちょうどにしたいです。その最小コストを求めてください。
クッキーを$A$枚ちょうどにできないときは$-1$を出力してください。

なお入力は$Q$クエリ与えられるので、それぞれに対して答えを求めてください。

入力

$Q$
$A_1\ B_1\ C_1$
$\vdots$
$A_Q\ B_Q\ C_Q$

入力は全て整数である
$1 \le Q \le 20$
$1 \le A_i,B_i,C_i \le 10^9\ (1 \le i \le Q)$

出力

$Q$行出力してください。
$A_i,B_i,C_i$をそれぞれ問題文中の$A,B,C$としてクエリに答えてください。
1クエリごとに改行してください。

サンプル

サンプル1
入力
1
7 1 3
出力
3

下記のように遷移することで$1×3=3$円で$7$枚にすることができます。
$\ 0$ (初期状態)
→ $(+2)\ 2\ $
→ $(×3)\ 6\ $
→ $(+1)\ 7\ $

サンプル2
入力
1
133 2 5
出力
12

下記のように遷移することで$2×6=12$円で$133$枚にすることができます。
$\ 0$ (初期状態)
→ $(+1)\ 1\ $
→ $(×5)\ 5\ $
→ $(×5)\ 25\ $
→ $(×5)\ 125\ $
→ $(+4)\ 129\ $
→ $(+4)\ 133\ $

サンプル3
入力
2
12345789 987654321 57
12 2 3
出力
7901234568
6

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。