[ONTAK2015]Badania naukowe

时间限制:3s      空间限制:256MB

题目描述

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


输入格式

第一行包含一个正整数n(1<=n<=3000),表示A串的长度。
第二行包含n个正整数,其中第i个数表示A[i](1<=A[i]<=1000)。
第三行包含一个正整数m(1<=m<=3000),表示B串的长度。
第四行包含m个正整数,其中第i个数表示B[i](1<=B[i]<=1000)。
第五行包含一个整数k(0<=k<=3000),表示C串的长度。
第六行包含k个正整数,其中第i个数表示C[i](1<=C[i]<=1000)。


输出格式

输出一个整数,即满足条件的最长公共子序列的长度,如果无解输出-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)。


题目来源

By Claris