Background

Genotype 是一个有限的基因序列集。它的每个成员都是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。
一个基因种类可以分化成为若干新的基因种类。这种 分化一般呈树状结构。树根处的基因序列称为母序列。
基因序列中含有母序列的基因子序列称为本质基因子序列。
生物信息学家们在研究Genotype 基因序列时，需要研究同一种类基因序列的相似性。
对于同一种类的2个基因序列X和Y，已知它们的母序列P，基因序列X和Y的最长公共本质基因子序列给出其相似性的准确刻画。
为了有效地分析基因序列的相似性，科学家们希望设计出一个高效的计算程序，能对给定的基因序列X，Y和它们的母序列P，快速计算出基因序列X和Y的最长公共本质基因子序列的长度。

Description

给定基因序列X，Y和母序列P，计算出基因序列X和Y的最长公共本质基因子序列的长度。 
数据输入:
输入数据的前3行中每行有一个正整数，分别表示序列X，Y和P的长度m，n和r（1≤m,n,r≤1000）。 接下来的3行给出序列X，Y和P。 

Format

Input

输入数据的前3行中每行有一个正整数，分别表示序列X，Y和P的长度m，n和r（1≤m,n,r≤1000）。 接下来的3行给出序列X，Y和P。

Output

输出基因序列X和Y的最长公共本质基因子序列的长度。如果基因序列X和Y没有以P为母序列的公共本质基因子序列，则输出0。

Sample 1

Input

3 3 1
ABC
BCA
A

Output

1

Sample 2

Input

11 10 2
AATGCCTAGGC
CGATCTGGAC
TG

Output

6

Limitation

1s, 1024KiB for each test case.
(不过我好像最后一个点给了两秒 —— Che_001)