Non-overlapping matches

We are required to implement special search functionality into a text editor. For a string entered by the user, this functionality has to look for similar substrings in the edited text. The aim is to find as many such non-overlapping substrings as possible and highlight them all at once.

The task

Given a text T, pattern P and threshold parameter D, find a set S of pairwise disjoint intervals <a, b>, where 1 ≤ a ≤ b ≤ |T|, that satisfy:

• For each <a, b> ∈ S, the Levenshtein distance between P and T(a)···T(b) is not greater than D.
• The size of S is largest possible.
• There is no other set of pairwise disjoint intervals S′ that fullfil all the above conditions (which means, among other things, that |S′|=|S|) and cover more characters of T than the intervals in S.

Remark: We assume that characters of T are indexed from 1 to |T|. Moreover, T(a)···T(b) is the substring of T starting at index a and ending at index b.

---

Input

The first input line contains a text T, the second input line contains a pattern P. Both sequences, T and P, are strings over {'a',...,'z'}. The third line contains an integer which is the similarity threshold parameter D.
It holds 1 ≤ D ≤ 23, D < |P| ≤ 180, 1 ≤ |T| ≤ 1.1 × 10⁶.

Output

The output is one line containing two integers, M and H, separated by space. M is the number of intervals in an optimal set S (i.e., the number of matches to be highlighted in the editor) and H is the number of characters of T that are not covered by any interval of S (i.e., the number of characters that will not be highlighted).

Example 1

Input

aabbbcabab
abb
1

Output

4 1

The result can be visualized as follows:

aab|bb|c|ab|ab

Characters to be highlighted are displayed in orange. Auxiliary characters '|' are added only here to separate matching substrings (they are not part of the text in the editor).

Example 2

Input

jedevvvede
jede
2

Output

3 1

The result can be visualized as follows:

je|de|v|vvede

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set