Alien Keyboard Typing

In this problem, you are given two strings: a keyboard string s of length n and an ancient artifact string t of length m. A movable pointer is initially placed at some position on s (its initial placement is free of cost) and can be moved left or right (but not outside the keyboard). At each position the pointer is on, you can press the key (i.e. output the character at that position).

The pointer is allowed to move a total distance of at most \(L\). Your task is to type a prefix of t (i.e. the first several characters of t) by moving the pointer on s and pressing the keys, such that the typed string is exactly equal to that prefix. Note that if the pointer is already on a key with the desired character, you can simply press it without moving.

Find the maximum number of characters (i.e. the length of the prefix of t) that can be typed on the keyboard under the constraint that the total pointer moving distance does not exceed \(L\).

Note: The cost is the sum of absolute differences of consecutive positions of the pointer. The initial placement is not counted in the cost.

inputFormat

The first line contains three integers n, m, and L, where n is the length of the keyboard string, m is the length of the artifact string, and L is the maximum allowed total pointer movement.

The second line contains the keyboard string s (of length n).

The third line contains the artifact string t (of length m).

outputFormat

Output a single integer representing the maximum number of characters from the prefix of t that can be typed while keeping the total pointer movement no more than \(L\).

sample

3 6 3
abc
abcabc

3