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

题目描述

小Q最近学习了KMP算法, 这是一个很厉害的字符串算法: 如果给定字符串 s 和 t, 那么通过KMP可以在线性的时间内算出 t 在 s 中所有出现的位置. 不妨设 , , 并规定角标从 1 开始计数, 那么 t 在 s 中所有的出现位置构成的集合可以表示为 .

将上述集合记为 P(s,t), 那么 P(s,t) 可能为空, 也可能包含很多个区间, 且还可能存在一个角标 i 被 P(s,t) 里的多个区间覆盖. 例如上述例子中 4 和 7 都被两个区间覆盖; 但当 ,  时, P(s,t) 里有 5 个区间, 且角标 3,4,5 被 P(s,t) 里面 3 个区间覆盖.

小Q不喜欢重复度很高的区间, 他希望找到一个 P(s,t) 的子集 , 使得对于每个角标 , i 至多被  里面至多 k 个区间覆盖. 但小Q又特别喜欢很大的集合, 因此他想知道  的最大值. 痴迷于出题的小Q想让你来帮他算出这个结果.

输入描述:

第一行包含用空格分开的三个整数 n,m,k (, ).

第二行一个长度为 n 的字符串 s, 第三行一个长度为 m 的字符串 t, 保证这两个字符串的字符都是小写拉丁字母.

输出描述:

输出一行一个整数, 表示  的最大值.
示例1

输入

复制 
7 3 2
aaaaaaa
aaa

输出

复制 
4
示例2

输入

复制 
10 4 1
aabaabaaba
aaba

输出

复制 
2