D-真爱粉Tk（三）_牛客周赛 Round 90

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 众所不周知，Tk 是坤的真爱粉，所以 Tk 对所有与 $25$ 有关的东西都极其敏感。一天邪恶的黑粉给 Tk 一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，Tk 找到了你，希望你将数组分割成 $k$ 个非空子区间 $[l_j,r_j]$ ，其中保证 $l_1=1,\; r_k=n$ 以及对于任意 $1<j\leqq k$ 都有 $r_{j-1}+1=l_j$ 。
$\hspace{15pt}$ 你要尽可能降低所有子区间中字符子序列 $25$ 的最大出现次数。请输出你操作后所有子区间中字符子序列 $25$ 的最大出现次数的最小值.
$\hspace{15pt}$ 字符子序列：在本题中，你可以理解为将数组区间中所有数字按顺序拼接成一个字符串，该字符串中的子序列即为该数组区间的字符子序列。例如，数组 $\{22,55\}$ 按顺序拼接成字符串 $2255$ ，该字符串中有 $4$ 个子序列为 $25$ ，则该数组的字符子序列 $25$ 个数为 $4$ .

输入描述:

第一行输入两个整数  表示数组大小以及要分割的子区间个数. 
第二行输入  个整数  表示数组 .

输出描述:

输出一个整数表示最小化子区间中字符子序列  出现次数的最大值.

示例1

输入

复制

5 2
22 55 5555 222 55

输出

复制

说明

 分割区间  和 后，第一个区间的字符子序列  个数为 ，第二个区间为 ，所以最终答案为 .