配点 : $300$ 点

問題文

高橋くんは整数を $1$ つ買いに整数屋さんに行きました。

整数屋さんには $1$ 以上 $10^9$ 以下の整数が売られていて、整数 $N$ を買うためには $A \times N + B \times d(N)$ 円が必要です。ここで、$d(N)$ は $N$ の十進表記での桁数です。

高橋くんの所持金が $X$ 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が $1$ つもない場合は $0$ を出力してください。

制約

• 入力は全て整数である。
• $1 \leq A \leq 10^9$
• $1 \leq B \leq 10^9$
• $1 \leq X \leq 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$ $X$

出力

高橋くんの買うことのできる最も大きい整数を出力せよ。ただし、買うことのできる整数が $1$ つもない場合は $0$ を出力せよ。

10 7 100

9

$9$ の値段は $10 \times 9 + 7 \times 1 = 97$ 円で、これが買うことのできる最大の整数です。 他の整数の値段の例をいくつかあげると

• $10: 10 \times 10 + 7 \times 2 = 114$ 円
• $100: 10 \times 100 + 7 \times 3 = 1021$ 円
• $12345: 10 \times 12345 + 7 \times 5 = 123485$ 円

です。

2 1 100000000000

1000000000

お店に売られている最大の整数を買うことができます。入力が $32$ bit整数型に収まらないことがあることに注意してください。

1000000000 1000000000 100

0

1234 56789 314159265

254309