Contest Duration: - (local time) (100 minutes) Back to Home
C - Buy an Integer /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

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

### 入力

A B X


### 入力例 1

10 7 100


### 出力例 1

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

2 1 100000000000


### 出力例 2

1000000000


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

### 入力例 3

1000000000 1000000000 100


### 出力例 3

0


### 入力例 4

1234 56789 314159265


### 出力例 4

254309


Score : 300 points

### Problem Statement

Takahashi has come to an integer shop to buy an integer.

The shop sells the integers from 1 through 10^9. The integer N is sold for A \times N + B \times d(N) yen (the currency of Japan), where d(N) is the number of digits in the decimal notation of N.

Find the largest integer that Takahashi can buy when he has X yen. If no integer can be bought, print 0.

### Constraints

• All values in input are integers.
• 1 \leq A \leq 10^9
• 1 \leq B \leq 10^9
• 1 \leq X \leq 10^{18}

### Input

Input is given from Standard Input in the following format:

A B X


### Output

Print the greatest integer that Takahashi can buy. If no integer can be bought, print 0.

### Sample Input 1

10 7 100


### Sample Output 1

9


The integer 9 is sold for 10 \times 9 + 7 \times 1 = 97 yen, and this is the greatest integer that can be bought. Some of the other integers are sold for the following prices:

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

### Sample Input 2

2 1 100000000000


### Sample Output 2

1000000000


He can buy the largest integer that is sold. Note that input may not fit into a 32-bit integer type.

### Sample Input 3

1000000000 1000000000 100


### Sample Output 3

0


### Sample Input 4

1234 56789 314159265


### Sample Output 4

254309