Number Concatenation

Time limit2sMemory limit128 MB

Summary

Given a subsequence left after deleting digits from the concatenation of 1,2,...,N, find the smallest N that could produce it.

Level: Hard8 of 10
Topics: String matching, Binary search, Greedy, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples8

Example 1
Input
```
1234
```
Expected output
```
4
```
Example 2
Input
```
234092
```
Expected output
```
20
```
Example 3
Input
```
999909
```
Expected output
```
49
```
Example 4
Input
```
82340329923
```
Expected output
```
43
```
Example 5
Input
```
32098221
```
Expected output
```
61
```
Example 6
Input
```
1111111
```
Expected output
```
14
```

Example 7

Input

00000000000000000000000000000000000000000000000000000000000000000000000

Expected output

Example 8

Input

345029834023049820394802334909240982039842039483294792934790209

Expected output