Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Zoba the Misleader

By Zeronfinity · Limits 1s, 512 MB

Zoba has 3 strings, named S1, S2 and S3. He wanted to make a tough problem for Mihaf with these strings.

Zoba said to Mihaf, “Here is a challenge for you. You have to find a palindromic substring from S1 in such a way that the length of this substring is maximum and an odd number greater than one. The number of unique characters in this substring must be at least K. After removing the character in middle of this substring, the new even-length palindromic substring must be a substring of string S2. Furthermore, the last half of this new substring also must be a substring of S3. Mihaf, you have to tell the length of the palindromic substring from S1 that will satisfy all these constraints. If fail to do so, you will have to pay the bill of my dinner tonight. And if you succeed, my bill of tonight’s dinner will be paid by you. Are you up for it?”

Mihaf thinks that he can easily win this challenge by coming to you, a great programmer who will write a code to find the answer for Mihaf. Can you do this?

Input

At the first line of input, you will be given an integer K (1 ≤ K ≤ 26), its description is in the problem statement.

Then each of the next 3 lines, the strings S1, S2 and S3 (1 ≤ Length of S1, S2, S3 ≤ 106) are given one by one. The characters in each of these strings are lowercase Latin letters.

Output

Find the length of the palindromic substring of S1 which satisfies the constraints of the problem description. If no such substring exists, print 0.

Samples

InputOutput
1
bcbaaaaa
bb
cb
3

Here, the optimal palindromic substring of S1 is bcb.

The number of unique characters in it is 2, which is larger than K.

When the middle character c is removed, it becomes bb, a palindromic substring of S2. Its last half is b, a substring of string S3.

Another palindromic substring of S1 is aaaaa which is not valid as aaaa is not a substring of S2.

InputOutput
3
bcbaaaaa
bb
cb
0

Here, the optimal palindromic substring of S1 is none since there is no palindromic substring of S1 where the number of unique characters is at least k=3.


A substring is a contiguous sequence of characters within a string. For instance, “the best of” is a substring of “It was the best of times”.


Discussion