Increasing Sequence

Time limit2sMemory limit128 MB

Summary

Given a digit string up to 80 characters, split it into a strictly increasing sequence of integers (leading zeros allowed) minimizing the last number's value.

Level: Medium7 of 10
Topics: Dynamic programming, String, Math
Solved: No attempts yet

Problem

You are given a string consisting only of decimal digits. Split it into one or more contiguous substrings to form a sequence. Each substring is interpreted as an integer, and leading zeroes are allowed.

After the split, the sequence must be strictly increasing: every number must be larger than the previous one. Among all valid increasing sequences, minimize the value of the last number and output that value.

Input

The first line contains the digit string. Its length is between 1 and 80, inclusive.

Output

Print the minimum possible value of the last number in a valid increasing sequence. If the last substring has leading zeroes, omit them when printing; if its value is 0, print 0.

Examples3

Example 1
Input
```
3456
```
Expected output
```
6
```
Example 2
Input
```
0001
```
Expected output
```
1
```
Example 3
Input
```
100000101
```
Expected output
```
101
```