Number Concatenation

If every integer from 1 through N is written in order without spaces, it forms a string such as 123456789101112...N.

Some digits were deleted from this string. It is also possible that no digit was deleted. The remaining digits keep their original order and are concatenated into one digit string.

Given the remaining digit string, find the smallest possible N that could have produced it.

The first line contains the digit string left after deletions. Its length is at most 3,000.

Print the smallest possible N that can produce the given string.