ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1165. Subnumber

Time limit: 1.0 second
Memory limit: 64 MB
George likes arithmetics very much. Especially he likes the integers series. His most favourite thing is the infinite sequence of digits, which results as the concatenation of all positive integers in ascending order. The beginning of this sequence is 1234567891011121314… Let us call this sequence S. Then S[1] = 1, S[2] = 2, …, S[10] = 1, S[11] = 0, …, and so on.
George takes a sequence of digits A and wants to know when it first appears in S. Help him to solve this difficult problem.

Input

The first line contains A - the given sequence of digits. The number of digits in A does not exceed 200.

Output

Output the only number - the least k such that A[1] = S[k], A[2] = S[k+1], ... A[len(A)] = S[k + len(A) – 1], where len(A) denotes the length of A (i.e. the number of digits in it).

Sample

inputoutput
101
10
Problem Author: Nikita Shamgunov
Problem Source: ACM ICPC 2001. Northeastern European Region, Northern Subregion