#4275. [ONTAK2015]Badania naukowe

题目描述

给定三个数字串A,B,C，请找到一个A,B的最长公共子序列，满足C是该子序列的子串。

输入格式

第一行包含一个正整数n(1<=n<=3000)，表示A串的长度。

第二行包含n个正整数，其中第i个数表示Ai。

第三行包含一个正整数m(1<=m<=3000)，表示B串的长度。

第四行包含m个正整数，其中第i个数表示Bi。

第五行包含一个整数k(0<=k<=3000)，表示C串的长度。

第六行包含k个正整数，其中第i个数表示Ci。

输出格式

输出一个整数，即满足条件的最长公共子序列的长度，如果无解输出-1。特别的，如果k为0且无解，请输出0。

样例

样例输入

7  

1 2 2 3 1 1 2  

6  

1 2 1 3 1 2  

2  

3 2

样例输出

4

数据范围与提示

找到的最长个公共子序列为(1,2,3,2)。