증가수열

숫자로만 이루어진 문자열을 하나 이상의 연속한 부분 문자열로 나누어 수열을 만들려고 한다. 각 부분 문자열은 하나의 정수로 해석하며, 부분 문자열 앞에 0이 붙어 있어도 된다.

나눈 뒤의 수열은 앞의 수보다 뒤의 수가 항상 큰 증가수열이어야 한다. 가능한 모든 증가수열 중 마지막 수의 값이 최소가 되도록 할 때, 그 마지막 수를 구하라.

첫째 줄에 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 1 이상 80 이하이다.

가능한 증가수열에서 마지막 수의 최솟값을 출력한다. 마지막 부분 문자열에 앞자리 0이 있으면 그 0은 생략하고 출력하며, 값이 0이면 0을 출력한다.