Mua một số nguyên (Buy an Integer)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cửa hàng bán các số nguyên từ $1$ đến $10^9$. Giá của số nguyên $N$ là

trong đó $d(N)$ là số chữ số của $N$ trong hệ thập phân.

Bạn có $X$ tiền. Hãy tìm số nguyên lớn nhất có thể mua. Nếu không mua được số nào, in $0$.

Input

Dòng duy nhất chứa $A,B,X$.

Output

In số nguyên lớn nhất mua được, hoặc 0.

Subtask

• Subtask 1 — 20%: $A,B,X\le10^6$.
• Subtask 2 — 30%: $X\le10^{12}$.
• Subtask 3 — 50%: $1\le A,B\le10^9$, $1\le X\le10^{18}$.

Ví dụ

Input

10 7 100

Output

9

Giải thích

Số $9$ có giá $10\cdot9+7\cdot1=97$. Số $10$ có giá $10\cdot10+7\cdot2=114>100$, nên đáp án là $9$.