#ABC146C. 买一个整数

买一个整数

AT_abc146_c [ABC146C] Buy an Integer

题目描述

\hspace{15pt}高桥君去整数商店买一个整数。

\hspace{15pt}商店里出售 11 到 10910^9 之间的整数。购买整数 nn 需要支付 a×n+b×d(n)a \times n + b \times d(n) 日元,这里 d(n)d(n) 表示 nn 的十进制位数。

\hspace{15pt}已知高桥君拥有 xx 日元,请你求出他能买到的最大的整数。如果没有任何整数可以买,则输出 00。

输入格式

\hspace{15pt}在一行上输入三个整数 $a, b, x \left(1 \leqq a, b \leqq 10^9;\ 1 \leqq x \leqq 10^{18}\right)$ 分别代表购买一个整数的价格系数 aa、位数价格系数 bb 和高桥君拥有的日元数。

输出格式

\hspace{15pt}在一行上输出一个整数,代表高桥君能买到的最大的整数。如果没有任何整数可以买,则输出 00。

测试样例

10 7 100
9

样例 1 解释

\hspace{15pt}整数 99 的价格为 10×9+7×1=9710 \times 9 + 7 \times 1 = 97 日元,这是可以购买的最大整数。其他整数的价格举例如下:

∙ \hspace{23pt}\bullet\,整数 1010 的价格为 10×10+7×2=11410 \times 10 + 7 \times 2 = 114 日元;

∙ \hspace{23pt}\bullet\,整数 100100 的价格为 10×100+7×3=102110 \times 100 + 7 \times 3 = 1021 日元;

∙ \hspace{23pt}\bullet\,整数 1234512345 的价格为 10×12345+7×5=12348510 \times 12345 + 7 \times 5 = 123485 日元。

2 1 100000000000
1000000000

样例 2 解释

\hspace{15pt}可以购买商店中出售的最大整数。注意输入可能超出 3232 位整数范围。

1000000000 1000000000 100
0
1234 56789 314159265
254309