Problem5715--流行数字

5715: 流行数字

Time Limit: 2.000 Sec  Memory Limit: 256 MB
Submit: 32  Solved: 9
[Submit] [Status] [Web Board] [Creator:]

Description

众所周知,1145141919是深受大家喜爱的流行数字。

你非常喜欢这个数字,为此你每天都要不知疲倦的、重复念出这个数字:114514191911451419191145141919...

有一天,你想要为这个流行数字创造更多的可能性。你决定为这个无限循环的1145141919中间增加左右括号、加号、乘号。当然,增加的括号、加号、乘号的数量由你自己决定,增加的位置也由你自行决定,甚至你也可以选择不加任何符号。

由于你总是从头开始读取这个流行数字,你现在想要知道,如何增加左右括号、加号、乘号,可以让你在尽量少读数字数目的情况下得到一个指定的数字。

例如你想得到520这个数字,你可以选择1+1+4+514,即通过增加3个加号,只需要读取前6个数字,就可以得到520了。


Input

输入一个整数N,表示想要得到的指定数字

Output

输出最少需要从头读取的数字个数。若无法得到指定数字,输出-1

Sample Input

520

Sample Output

6

HINT

【数据范围】

10%的数据,N<=10

100%的数据,N<=5000

Source/Category

 

[Submit] [Status]