Longest Common Subsequence
You are given two sequences, a and b, of lengths n and m respectively. Your task is to find the length of the longest common subsequence of the two sequences.
Input
The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 1000).
The second line contains n space-separated integers , representing the elements of sequence a (1 ≤ ≤ ).
The third line contains m space-separated integers , representing the elements of sequence b (1 ≤ ≤ ).
Output
Print a single integer - the length of the longest common subsequence of a and b.
Examples
Input | Output |
|---|---|
5 4 2 1 5 3 4 2 5 1 4 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB