Longest Common Subsequence

Given two sequences of integers, your task is to compute the length of their longest common subsequence (LCS). The LCS is defined as the longest sequence that appears in both original sequences (not necessarily consecutively).

For two sequences (A) and (B) of lengths (m) and (n) respectively, define a 2D array (dp) such that [ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } A[i] = B[j]
\max(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases} ] The final answer is given by (dp[m][n]).

Your program should read the input from stdin and output the result to stdout.

inputFormat

The input consists of two lines. The first line contains a sequence of space-separated integers representing the first sequence. The second line contains a sequence of space-separated integers representing the second sequence. If a line is empty, it represents an empty sequence.

outputFormat

Output a single integer which is the length of the longest common subsequence of the two sequences.## sample

1 3 4 1 2 5
1 4 1 2 5

5