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.
import sys

def fill_map():
    mp = {}
    curr = 1
    i = 1
    while i <= 10**16:
        mp[i] = curr
        i *= 10
        curr += 1
    return mp

def check(mid, w, m, k, mp):
    cost = 0
    curr = m
    for key, value in mp.items():
        if key < curr:
            continue
        else:
            if key > mid:
                left = mid - curr
                cost += (left * (value - 1) * k)
                curr = mid
                break
            else:
                left = key - curr
                cost += (left * (value - 1) * k)
                curr = key
    return cost <= w

def solve():
    mp = fill_map()
    w, m, k = map(int, input().split())
    low, high = m, 10**18
    ans = 0
    while low <= high:
        mid = (low + high) // 2
        if check(mid, w, m, k, mp):
            ans = mid - m
            low = mid + 1
        else:
            high = mid - 1
    print(ans)

if __name__ == "__main__":
    # If you want to read input from a file, uncomment the next two lines:
    # sys.stdin = open('input.txt', 'r')
    # sys.stdout = open('output.txt', 'w')
    
    import time
    start_time = time.time()
    
    solve()
    
    end_time = time.time()
    execution_time = (end_time - start_time) * 1000  # Convert to milliseconds
    print("Time:", execution_time)
