题目描述

想要背诵一段很长的数字，比如圆周率，可以将这些数字分割成一个个片段，根据每个片段的规律做不同的记忆训练。不妨假定每个片段最少 $3$ 个数，最多 $6$ 个数，各种片段的记忆难度定义如下：

• 若所有数字相同，如 666，88888 等，则记忆难度为 $1$；
• 公差为 $1$ 或者 $-1$ 的等差数列，如 3456，43210 等，记忆难度为 $2$；
• 两个数字交替出现，如 313，68686 等，记忆难度为 $4$；
• 其他等差数列，如 7531，369 等，记忆难度为 $5$，但注意 36912 不算等差数列，因为我们只考虑一位数字；
• 不属于上述任何一条规律的，比如 2794 等，记忆难度为 $10$。

现在给定一个由数字构成的字符串 $s$，请找出一个分割片段的方法，使得所有片段的记忆难度之和最小。

输入格式

一个由数字构成的字符串 $s$。

输出格式

单个整数：表示记忆难度之和的最小值。

314159265358979323846

34

样例解释 1

分成(314159)(265358)(979)(323846)，总难度为10+10+4+10=34

271828182845904523536

40

样例解释 2

分成(271828)(182845)(904523)(536)，总难度为40

12122222

5

样例解释 3

分成(1212)(2222)，总难度4+1=5

数据范围

设 $s$ 的长度为 $n$，则

• 对 $30\%$ 的数据 $3\leq n\leq 20$；
• 对 $60\%$ 的数据 $3\leq n\leq 10000$；
• 对 $100\%$ 的数据 $3\leq n\leq 100000$。