Comet OJ

C1079 [Contest #5]迫真字符串

内存限制：256 MB 时间限制：1000 ms

题目描述

本次比赛的主人公是H君，大家都喜欢叫他HE指导，他的爱好是荒野行动和王道征途。

H君已经24岁了，作为大龄学生的他准备用一个字符串庆祝自己的生日，H君称这个字符串 $S$ 为迫真字符串。

迫真字符串是一个仅由数字 '0' 至 '9' 组成的字符串，H君现在觉得这个字符串 $S$ 还不够优雅，他决定对字符串 $S$ 进行重新排列，使得连续子串"114514" 在重新排列后的 $S$ 中出现的次数尽可能多（可以重叠）。

注：若能把字符串 $s$ 重新排列成字符串 $t$，当且仅当每一个字符在 $s$ 和 $t$ 出现的次数都相等，举例来说："12330" 中 0,1,2各出现 $1$ 次，$3$ 出现两次，故可以重新排列成 "02331" 或是 "30123"，但不能重新排列成 "12203" 及 "0123"。

输入格式

第一行一个由数字 '0' 至 '9' 组成字符串 $S$。

数据范围：

令整数 $n$ 为字符串 $S$ 的长度，$1\leq n \leq 2 \times 10^5$

输出

第一行一个数，表示重新排列后连续子串 "114514" 在 $S$ 中能出现的最大次数。

样例

样例输入 1

1145141

样例输出 1

1

样例输入 2

000012345671111111871543253456719816513234

样例输出 2

2

提示

样例解释 1：

H君不需要排列这个字符串S，即令排列后的字符串就等于 $S$，肉眼可见 "114514"，可以证明这是最大出现次数。