We'll define *S*(*n*) for positive integer *n* as follows: the number of the *n*'s digits in the decimal base. For example, *S*(893) = 3, *S*(114514) = 6.

You want to make a consecutive integer sequence starting from number *m* (*m*, *m* + 1, ...). But you need to pay *S*(*n*)·*k* to add the number *n* to the sequence.

You can spend a cost up to *w*, and you want to make the sequence as long as possible. Write a program that tells sequence's maximum length.
The first line contains three integers *w* (1 ≤ *w* ≤ 10<sup class="upper-index">16</sup>), *m* (1 ≤ *m* ≤ 10<sup class="upper-index">16</sup>), *k* (1 ≤ *k* ≤ 10<sup class="upper-index">9</sup>).

Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int mx = 100010;


ll w,k;

bool can(ll mid,ll m) {
    ostringstream s1,s2;
    ll temp = 1,gold = w;
    s1 << mid;
    s2 << m;
    //cout << mid << " : " << m << endl;
    if(s1.str().length() == s2.str().length()) {
        if((mid-m+1)*s1.str().length()*k <= w) return 1;
        else return 0;
    }
    else {
        for(int i=0;i<s1.str().length()-1;i++) temp *= 10;
        for(int i=s2.str().length();i<=s1.str().length();i++) {
            if(i == s2.str().length()) {
                //cout << "GOLD: " << gold << endl;
                //cout << temp << " " << m << " " << i << endl;
                //cout << (temp-m)*i*k << endl;
                if(gold >= (temp-m)*i*k) gold -= (temp-m)*i*k;
                else return 0;
            }
            else if(i == s1.str().length()) {
                //cout << "GOLD 2: " << gold << endl;
                //cout << temp/10 << " " << mid << " " << i << endl;
                //cout << (mid-temp/10+1)*i*k << endl;
                if(gold >= (mid-temp/10+1)*i*k) {
                    gold -= (mid-temp/10+1)*i*k;
                }
                else return 0;
            }
            else {
                if(gold >= (temp*10-temp)*i*k) gold -= (temp*10-temp)*i*k;
                else return 0;
            }
            temp *= 10;
        }
    }
    return 1;
}

int main() {
    ll m,a,b;
    scanf("%I64d %I64d %I64d",&w,&m,&k);
    a = 0;
    b = w/k+10;
    while(b-a > 1) {
        //cout << a << " " << b << endl;
        ll mid = (a+b)/2;
        //cout << mid << endl;
        if(can(mid+m-1,m)) a = mid;
        else b = mid-1;
        //if(mid == 4) return 0;
    }
    if(can(b,m)) printf("%I64d\n",b);
    else printf("%I64d\n",a);
}
