You are given three strings, ~P,S,T~. We will define the score of a substring ~M~ of ~S~ as the sum of the length of the longest suffix of ~P~ that is a prefix of ~M~ and the length of the longest prefix of ~T~ that is a suffix of ~M~. Find the highest possible score of any such substring of ~S~. Each string will only contain lowercase letters.

Subtasks

1. (40 points) ~1 \leq |P|,|S|,|T| \leq 200~
2. (60 points) ~1 \leq |P|,|S|,|T| \leq 10^5~

Input Specification

The first line will contain the string ~P~, the second will contain ~S~, and the third ~T~.

Output Specification

A single integer, denoting the largest achievable score of any substring of ~S~.

Sample Input 1

abc
abcdef
f

Sample Output 1

4

Sample Input 2

aa
aa
aa

Sample Output 2

4