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.💡
A subsequence is a new sequence obtained by deleting some (or none) of the elements of the original sequence, without changing the order of the remaining elements.
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 a (1 ≤ ≤ ).
The third line contains m space-separated integers 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