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\le |P|,|S|,|T|\le 200$
2. (60 points) $1\le |P|,|S|,|T|\le {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