遗迹

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

3 6 5
abc
acbbac

样例输出 #1

5

提示

【样例说明】

初始选择指针位于键盘 $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$ 中出现过的字母，数据保证随机。