该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小蓝找到了一个外星文明留下来的遗迹，遗迹大门的屏幕上有一个长度为 $m$ 的字符串 $t$ 和一个输入框，下面还有一个键盘，键盘为一个长度为 $n$ 的字符串 $s$，由一个可以横向移动的指针来敲击键盘，指针可以向左移或向右移，不能移出键盘。

小蓝需要在键盘字符串 $s$ 上先指定指针初始位置然后不断移动指针的位置，过程中通过敲击指针所在的字符来进行输入。然而，指针最多只能移动 $L$ 的距离，小蓝想输入一个尽可能长的一个 $t$ 的前缀，请问他最多能输入多少位。

输入格式

输入的第一行包含三个正整数 $n,m,L$，相邻整数之间使用一个空格分隔。

第二行包含一个长度为 $n$ 的字符串 $s$。

第三行包含一个长度为 $m$ 的字符串 $t$。

输出格式

输出一行包含一个整数表示答案。

3 6 5 
abc 
acbbac

5

数据范围

对于 $20\%$ 的评测用例，$1≤m≤20$;

对于所有评测用例，$1≤n≤10^3$，$1≤m≤10^5$，$1≤L≤10^9$ 且 $s,t$ 中只包含小写字母，且 $s$ 中一定包含所有 $t$ 中出现过的字母，数据保证 $s$ 随机生成。

额外挑战

数据不保证 $s$ 随机生成。