Amusing Numbers

Time limit1sMemory limit128 MB

Summary
Given K and M, find the smallest N such that K sits at lexicographic position M among the numbers 1 to N.
Level

Medium7 of 10

Topics
Math, Binary search, Implementation, Trie
Solved
No attempts yet

Problem

Consider the integers from 1 to N inclusive. Order them lexicographically (that is, as in a dictionary). For example, for N = 11 the order is:

1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

Let QN,KQ_{N,K} denote the position (counting from 1) of the number K in this ordering. For example, Q11,2=4Q_{11,2} = 4.

Given K and M, find the smallest N such that QN,K=MQ_{N,K} = M.

Input

A single line with two integers K and M (1≤K,M≤1091 \le K, M \le 10^9), separated by a space.

Output

If an N with QN,K=MQ_{N,K} = M exists, print the smallest such N. Otherwise, print 0.

Examples4

  1. Example 1

    Input
    2 4
    
    Expected output
    11
    
  2. Example 2

    Input
    2 1
    
    Expected output
    0
    
  3. Example 3

    Input
    100000001 1000000000
    
    Expected output
    100000000888888879
    
  4. Example 4

    Input
    1000000000 11
    
    Expected output
    0