题目描述

由于遭受了百年一遇的寒潮，安东诺夫家在诺夫哥罗德的牧场暂时无法继续运作。他准备启用位于远东的布里亚特共和国（俄罗斯联邦内的一个自治共和国）的预备牧场。临行前，他决定出售其中的一头奶牛给他的朋友巴兰尼科夫。奶牛的重量不大于 $10^9$。

对于安东诺夫的奶牛，巴兰尼科夫打算这样出价：

给定 $a,b,x$ 三个整数。

若出售的奶牛重量 $p$ 千克，且 $p$ 在十进制下为 $q$ 位，那么奶牛的价格是 $ap + bq$ 卢布。

（注意：$p=0$ 时，$q$ 也等于 $0$）

巴兰尼科夫的预算为 $x$ 卢布，他想知道在不超过预算的前提下他买到的奶牛的重量的最大值。

输入格式

一行三个数 $a,b,x$。

• $1\ \leq\ a\ \leq\ 10^9$
• $1\ \leq\ b\ \leq\ 10^9$
• $1\ \leq\ x\ \leq\ 10^{18}$

输出格式

巴兰尼科夫能买到的奶牛的重量的最大值。

10 7 100

9

2 1 100000000000

1000000000

1000000000 1000000000 100

0