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

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例

3 6 5 
abc 
acbbac

5

解释 #1

初始选择指针位于键盘 $abc$ 上的 $a$，输入 $acbbac$ 这 $6$ 个字符分别需要指针 移动 $0, 2, 1, 0, 1, 2$ 的距离，而最大移动距离为 $5$，所以最多输入 $5$ 个字符，移动 $0 + 2 + 1 + 0 + 1 = 4$ 的距离。

数据范围

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