Longest Common Increasing Subsequence

Given two sequences A and B, find the length of their Longest Common Increasing Subsequence (LCIS).

A subsequence is obtained by deleting some or no elements without changing the order of the remaining elements. An increasing subsequence is one in which every element is strictly larger than its previous element. The LCIS is defined as the longest subsequence that is common to both A and B and is strictly increasing.

Formally, given two sequences A and B, if there exists a sequence \(S = [s_1, s_2, \dots, s_k]\) such that \(s_1 < s_2 < \dots < s_k\) and S is a subsequence of both A and B, then the length of S is a candidate, and the maximum such \(k\) is the answer.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the lengths of sequences A and B respectively.

The second line contains \(n\) integers denoting the elements of sequence A.

The third line contains \(m\) integers denoting the elements of sequence B.

outputFormat

Output a single integer — the length of the Longest Common Increasing Subsequence of the two sequences.

sample

5 4
1 2 3 2 4
1 2 2 4

3