Alien Relic Keyboard Path

Xiao Lan has discovered remnants of an alien civilization. On the massive door of the relic, there are two things: a screen showing a string \(t\) of length \(m\) and a keyboard displaying a string \(s\) of length \(n\). A movable pointer is used to strike the keys on the keyboard. You can initially set the pointer at any position of \(s\) without any cost. Then you can repeatedly move the pointer left or right (without leaving the keyboard) and press the key at the pointer to input its character. However, the pointer can be moved a total distance of at most \(L\) (i.e. the sum of the absolute differences between successive positions is at most \(L\)).

Xiao Lan wishes to input as long a prefix of \(t\) as possible. In other words, by choosing an initial position and then a sequence of moves (with total moving cost \(\le L\)), he wants the sequence of pressed keys (i.e. the characters from \(s\) at the visited positions) to match the first \(k\) characters of \(t\) for as large a \(k\) as possible.

Your task is to determine the maximum number \(k\) (possibly 0) such that it is possible to input the first \(k\) characters of \(t\) using the described process.

Note: When the pointer is at a position, the character at that position is pressed and appended to the input string. The initial pointer placement does not incur any move cost.

inputFormat

The first line contains three integers \(m\), \(n\), and \(L\) \((1 \le m, n \le 10^5,\; 0 \le L \le 10^9)\), representing the length of \(t\), the length of \(s\), and the maximum total move distance of the pointer.

The second line contains the string \(t\) of length \(m\) composed of lowercase letters.

The third line contains the string \(s\) of length \(n\) composed of lowercase letters.

outputFormat

Output a single integer: the maximum number of characters of the prefix of \(t\) that can be input without exceeding a total pointer moving distance of \(L\).

sample

5 6 3
aabaa
aabbaa

4